python - 查找列表中不构成配对的奇数

Question

我有一个问题需要解决!这是

给出一个由N个整数组成的非空数组A。该数组包含奇数个元素，并且数组的每个元素都可以与具有相同值的另一个元素配对，但一个未配对的元素除外。

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)

给定一个由满足上述条件的 N 个整数组成的数组 A，返回未配对元素的值。

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

我会选择reduce() (在 Python 3.x 中移至 functools.reduce())与 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) 解决方案。