查找数组中未配对的元素

Question

所以我刚刚通过解决我发现的一些示例问题（您可以在其中检查解决方案的正确性和时间复杂度）来开始自学算法，并且对一个问题特别困惑。

在这个问题中，我得到了一个包含奇数个整数元素的数组，其中数组的每个元素都可以与另一个具有相同值的元素配对，除了一个元素未配对。问题是要我找到这个不成对的元素。我尝试使用的功能在 python;

下方

def solution(A):
    
    N = len(A)   # constant
    if N == 1:   # constant
        return A[0]

    mergesort(A)   # NlogN

    if A[-1] != A[-2]:  # constant
        return A[-1]

    for i in range(0,N-1,2):   # apparently not linear?
        if A[i] != A[i+1]:
            return A[i]

为什么这是 O(N^2)，而不是 O(NlogN)？

我能想到的唯一原因是 A[i] 和 A[i+1] 的比较本身就是 O(N)，但我不明白为什么它不是常量。

任何帮助将不胜感激，感谢阅读！

Answer 1

正如 Abhinav Mathur 在评论中所说，您的算法可能需要是线性的，而不是 O(n log n)。

这是一个在线性时间内运行的解决方案，它利用了 XOR 运算和运算的以下属性：

XOR 是可交换的。即x ^ y = y ^ x.
任何与自身异或的数字都是0。即x ^ x = 0.
任何与 0 异或的数字都是它本身。即x ^ 0 = x.

如果我们将所有数字异或在一起，所有出现两次的数字将在我们的异或结果中产生 0。每当我们将零值与只出现一次的数字进行异或时，我们就会得到只出现一次的数字。

所以，我们的答案是将数组中的所有数字异或在一起的结果：

def solution(A):
    result = 0
    for item in A:
        result ^= item
    return result

或者如果您喜欢 one-liners，请使用 functools.reduce():

from functools import reduce
from operator import xor

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

如果我们假设异或运算需要常数时间，那么这个算法在线性时间内运行。

您也可以使用哈希集或 collections.Counter() 来解决此问题，但它们将使用线性数量的内存。这种方法使用常量内存。

查找数组中未配对的元素

Finding unpaired element in an array

python

algorithm

time-complexity