Geek Answers Handbook

Search for an odd number in an array

I am trying to solve a problem when I am given an array, such as [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10], where all numbers are duplicated twice, excluding one number, and I need to return a number that is not duplicated.

I am trying to do it like this:

def findNumber(self, nums):

    if (len(nums) == 1):
        return nums[0]

    nums_copy = nums[:]

    for i in nums:
        nums_copy.remove(i)

        if i not in nums:
            return i
        else:
            nums_copy.remove(i)

However, when it reaches the else statement, the following error occurs:

ValueError: list.remove (x): x is not in the list

This happens when it iis in nums_copy, so I do not understand why this error occurs in this situation?

+6
source share
8 answers

You already nums_copy.remove(i)so you cannot nums_copy.remove(i)again

You can do:

a = [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10]

def get_single_instance(array):
  d = {}

  for item in a:
    if item not in d:
      d[item] = 1
    else:
      d[item] += 1

  print d

  for k, v in d.iteritems():
    if v == 1:
      return k

print get_single_instance(a)

Result: 9

+6
source

( ) , , - Counter object:

 from collections import Counter

 singlet = Counter(nums).most_common()[-1][0]

Counter , , , , , . most_common (value, count), .

, , :

[k for k, v in Counter(nums).items() if v == 1]

:

, , , remove, in, - O (n 2). Counter . , , most_common , , O (n log n). @Stefan Pochman : Python Timsort, ( , , , ), O (n).

+10

- XOR .

def find_number(nums):
    s = 0 
    for n in nums:
        s ^= n 
    return s 


a = [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10] 
print(find_number(a))
+4

. , , , . :

a=[0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10]
[e for e in a if a.count(e)==1][0]
+2

, O(log n) O(1) . , , :

              0  1  2  3  4  5  6  7  8  9   10
             [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10]
even indexes: x     x     x     x
odd indexes:                             x

search:                      ^  (0 + 11) / 2 = 5
                         [2, 2] pair starting on even index
                                so the singleton must be ahead

                                      ^  (6 + 11) / 2 = 8
                                     [9] singleton found in two steps!
+2

. , nums_copy.remove(i), , count():

def findNumber(self, nums):

    for i in nums:

        val = nums.count(i)

        if val == 1:
            return i

. , , . , :

def findNumber(self, nums):
    values = []
    for i in nums:

        val = nums.count(i)

        if val == 1:
            values.append(i)

    return values
+1

( ), :

import more_itertools as mit


iterable = [0, 0, 1, 1, 2, 2, 6, 6, 9, 10, 10] 
next(x for x, y in mit.windowed(iterable, n=2, step=2) if x != y)
# 9

:

next(x for x, y in mit.sliced(iterable, 2) if x != y)
# 9

more_itertools - , > pip install more_itertools.

+1

, NumPy, :

>>> def get_single_instance_np(arr: np.ndarray):
...     return np.asscalar(arr[np.bincount(arr) == 1])

>>> print(get_single_instance(a))
9

, 1.

0

More articles:


All Articles