Нахождение нечетного целого числа, которое не образует пару в списке

Question

Мне дано решение проблемы!

1002 * Дан непустой массив A, состоящий из N целых чисел.Массив содержит нечетное количество элементов, и каждый элемент массива может быть связан с другим элементом с таким же значением, за исключением одного элемента, который остается непарным.

For example, in array A such that:   A[0] = 9  A[1] = 3  A[2] = 9   A[3] = 3  A[4] = 9  A[5] = 7   A[6] = 9

    the elements at indexes 0 and 2 have value 9,
    the elements at indexes 1 and 3 have value 3,
    the elements at indexes 4 and 6 have value 9,
    the element at index 5 has value 7 and is unpaired.

Напишите функцию:

def solution(A)

, что, учитывая массив A, состоящий из N целых чисел, удовлетворяющих вышеуказанным условиям, возвращает значение непарного элемента.

For example, given array A such that:
  A[0] = 9  A[1] = 3  A[2] = 9
  A[3] = 3  A[4] = 9  A[5] = 7
  A[6] = 9

функция должна возвращать 7, как объяснено впример выше.

Напишите эффективный алгоритм для следующих предположений:

    N is an odd integer within the range [1..1,000,000];
    each element of array A is an integer within the range [1..1,000,000,000];
    all but one of the values in A occur an even number of times.

Я думаю, что я только наполовину решил проблему:

def findOddItem(A):
    for i, item in enumerate(A): # look to left not immidiate one
        if A[i] != A[i - 2]:
            print A[i]

но этопохоже на печать неправильный результат ..

Answer 1

Вы можете использовать битовый оператор "xor".Поскольку все элементы встречаются дважды, кроме одного, они отменяют друг друга, оставляя элемент, который произошел только один раз.

def SingleOccurance( arr, n): 

result = arr[0] 

# Do XOR of all elements and return as 'a' xor 'a' is 0 and except single 
# occured number rest will turn to 0 and 'a' xor 0 is 'a'
for i in range(1,n): 
    result = res ^ arr[i] 

return result

или

Мы можем суммировать биты в одинаковых позициях для всехчисла и принимают по модулю с 3. Биты, для которых сумма не кратна 3, являются битами числа с одним вхождением.

Давайте рассмотрим примерный массив {5, 5, 5, 8}.101, 101, 101, 1000

Сумма первых битов% 3 = (1 + 1 + 1 + 0)% 3 = 0

Сумма вторых битов% 3 = (0 +0 + 0 + 0)% 0 = 0

Сумма третьих битов% 3 = (1 + 1 + 1 + 0)% 3 = 0

Сумма четвертых битов% 3 = (1)% 3 = 1 Следовательно, число, которое появляется один раз, равно 1000

Код:

INT_SIZE = 32

def getSingle(arr, n) : 

    # Initialize result 
    result = 0

    # Iterate through every bit 
    for i in range(0, INT_SIZE) : 

        # Find sum of set bits  at ith position in all array elements 
        sm = 0
        x = (1 << i) 
        for j in range(0, n) : 
            if (arr[j] & x) : 
                sm = sm + 1

        # The bits with sum not multiple of 3, are the 
        # bits of element with single occurrence. 
        if (sm % 3) : 
            result = result | x 

    return result 

Answer 2

Поскольку нет условия, что все элементы, кроме одного, встречаются дважды , я думаю, это также может означать 4, 6, ..., раз.

В этом случае я бы предпочел использовать numpy.bincount, чтобы увидеть, какое целое число имеет нечетное число.

a = [1,1,2,2,3,3,5,3,3,4,5,5,5,10,10]
a_cnt = list(numpy.bincount(a))
for i in a_cnt:
    if i != 0 and i%2 == 1:
        print(a_cnt.index(i))
# 4

Answer 3

Я бы пошел с reduce() (перемещено в functools.reduce() в Python 3.x) в сочетании с operator.xor():

# Uncomment for Python 3.x:
# from functools import reduce
import operator

def solution(A):
    return reduce(operator.xor, A)

arr = [9, 3, 9, 3, 9, 7, 9]

print(solution(arr))  # 7

Это, как ни крути, чистое решение O(n).

Answer 4

Вы можете использовать "или" побитовый оператор.Поскольку все элементы встречаются дважды, кроме одного, они отменяют друг друга, оставляя элемент, который произошел только один раз.

def findSingleOccurance( arr, n): 

    res = arr[0] 

    # Do XOR of all elements and return 
    for i in range(1,n): 
        res = res ^ arr[i] 

    return res 

Сложность времени O (n) Сложность пространства O (1).Надеюсь, это поможет.