在一个数组中找出只出现一次的数字的算法，假设其他数字都出现了两次

Question

我能想到的方法:

算法:

1. 使用哈希表来存储数字及其出现次数
2. 遍历数组并增加数字的计数
3. 然后遍历哈希表以获取计数为1的数字

你们有没有比这更好的解决方案。需要O(n)的运行时间且不使用额外的空间。

- Learner

---

这是一个相当不错的解决方案，效率也很高。 - glasnt

这是一道作业题吗？如果是的话，没关系，因为你已经很好地提出了问题，并且给出了你尝试解决它的方法。但是如果是作业题，你应该标记一下。 - Tim Jarvis

顺便说一句，“parse”这个词，我不认为它的意思是你所想的那样。 - Steve Jessop

为什么选择Rosetta Stone？BRad - Learner

这怎么可能被标记为一个六年后才提出的问题的重复？ - paxdiablo

Answer 1

假设您可以使用XOR运算符，这是关键所在，因为它具有以下属性：

• XOR是可交换和可结合的（因此执行顺序无关紧要）。
• 一个数与自身进行XOR操作将始终为零。
• 零与一个数字进行XOR操作将得到该数字。

因此，如果您只是将所有值简单地XOR在一起，所有出现两次的数字都会相互抵消（得到0），而剩下的数字(n)将与该结果(0)进行XOR操作，以得到n。

r = 0
for i = 1 to n.size:
    r = r xor n[i]
print "number is " + r

不需要哈希表，这个方法具有O(n)的性能和O(1)的额外空间（只使用了一个小整数）。

- paxdiablo

---

仅仅通过可交换性是不足以证明“执行操作的顺序无关紧要”，还需要结合结合律。方便的是，异或运算也具有结合律。为了理解为什么两者都需要，考虑一下（满足可交换性的）成对平均数函数：average(average(2, 4), 8) = 5.5，但是average(2, average(4, 8)) = 4。 - Doug McClean

我会听从你的判断，@Doug - 我已经超过20年没有做那个级别的数学了 :-) - paxdiablo

假设“number”作为POD行为，这将在内部实现方式如何的情况下都能正常工作 - 即使浮点数被读取为原始数据块也可以正常工作。非常优秀的解决方案。 - sharptooth

这种技术对负数也适用吗？我尝试了{-1，-1，-2}，但它返回3而不是-2！ - Hengameh

@Hengameh：那么你使用的语言可能无法正确执行xor，或者你的输出有误。你应该提出一个问题，展示你的代码并指明你使用的编程语言。这样，你将得到比仅仅向我提问更广泛的回应。 - paxdiablo

Answer 2

在Ruby中的一个答案，假设只有一个单例，其余的恰好出现两次：

def singleton(array)
  number = 0
  array.each{|n| number = number ^ n}
  number
end

irb(main):017:0> singleton([1, 2, 2, 3, 1])
=> 3

顺便说一下，^是按位异或运算符。异或一切!哈哈哈!

Rampion提醒了我inject方法，所以你可以在一行中完成这个操作:

def singleton(array) array.inject(0) { |accum,number| accum ^ number }; end

- Michael Sofaer

---

翻译：这是一个使用 array.inject(0) { |accum,number| accum ^ number } 的代码片段。 简述：使用该代码片段对数组进行操作。 - rampion

我并不认为一个 ruby 程序员会精通位运算，（我）躲开。 - poundifdef

等效的 Python 一行代码：def singleton(array): return reduce(lambda x,y:x^y, array) - Adam Rosenfield

@Michael - 这个词是“吸收”- 抵抗是徒劳的 ;) - rampion

我正在进行Haskell的“代码高尔夫”，翻译成中文为：singleton = foldr xor 0。意思是将列表中的所有元素通过异或运算（xor）合并到一个数值中，最终结果就是这个数值。 - R. Martinho Fernandes

Answer 3

解析数组并为数字增加计数。

您可以将其更改为“解析数组，如果该数字已经存在于哈希表中，则从哈希表中删除该数字”。 然后第三步只是“获取仍留在哈希表中的唯一数字”。

- Chris J

---

+1，不确定为什么被踩了。对我来说看起来非常合理。在哈希表中查找和删除项都应该是O(1)。 - Seth

O(1)? 你必须考虑调整大小（http://en.wikipedia.org/wiki/Hash_table）。我建议在最开始使用.resize()，因为你知道数组的大小。无论如何，使用XOR的解决方案更有效。 - MadH

当谈到像工作面试这样的事情时，使用“+1”的方式实际上是解决这个问题的首选方法。在我看来，“XOR”实在是太聪明了，不应该是面试者首先想到的东西。 - illegal-immigrant

Answer 4

给定一个整数数组，除了一个元素之外，每个元素都出现两次。找到那个单独的元素。 我们可以使用异或运算。因为每个数字与自身异或的结果将为零。所以我们对数组中的每个整数进行异或运算，结果就是我们要找的单一元素。 以下是Java版本的代码：

public class Solution {
    public int singleNumber(int[] A) {
        int res=0;
        for(int i=0;i<A.length;i++){
            res=res^A[i];
        }
        return res;
    }
}

跟进1： 给定一个整数数组，除了一个元素之外，每个元素都出现三次。找到那个单独的元素。 注意： 你的算法应该具有线性时间复杂度。你能实现它而不使用额外的内存吗？ 对于这个问题，我们不能使用XOR操作。解决这个问题的最佳方法是使用"位计数"。 创建一个32长度的int数组count[32]。 count[i]表示所有整数第ith位中'1'的数量。如果count[i]可以被3整除，则忽略这一位，否则我们将取出这一位并形成结果。下面是Java版本的代码：

public class Solution {
    public int singleNumber(int[] A) {
        int res=0;
        int[] count=new int[32];
        for(int i=0;i<32;i++){
            for(int j=0;j<A.length;j++){
                if(((A[j]>>i)&1)==1){
                    count[i]=count[i]+1;
                }
            }
            if((count[i]%3)!=0){
                res=res|(1<<i);
            }
        }
        return res;
    }
}

跟进2： 给定一个整数数组，除了两个数字，其余每个元素都出现两次。找到这两个数字。 解决方案： 首先，将数组中的所有整数进行异或操作，我们可以得到一个结果。（假设为c） 其次，从最低位到最高位，找到第一个“1”的位置（假设该位置为p）。 第三，在将整数分成两组时，p位置在其中一组中为“1”，另一组为“0”。 第四步，对两组中的所有整数进行异或操作，结果就是我们要找的两个整数。

- jerry

---

真的很棒的跟进 :) - Ivan Xiao

这种技术对负数也适用吗？我尝试了{-1，-1，-2}，它返回的是3而不是-2！ - Hengameh

Answer 5

我将翻译成中文：

我正在借鉴Michael Sofaer的答案，并在Python和C中重新实现：

Python:

def singleton(array):
    return reduce(lambda x,y:x^y, array)

C:

int32_t singleton(int32_t *array, size_t length)
{
    int32_t result = 0;
    size_t i;
    for(i = 0; i < length; i++)
        result ^= array[i];
    return result;
}

当然，C语言版本只适用于32位整数（如果您需要，可以轻松更改为64位整数）。Python版本没有这样的限制。

- Adam Rosenfield

---

这种技术对负数也适用吗？我尝试了{-1，-1，-2}，它返回的是3而不是-2！ - Hengameh

Answer 6

以下是Python中的解决方案，相比Ruby版本更小（并且在我看来更易读）:

singleton = lambda x: reduce(operator.xor, x)

- Nick Johnson

Answer 7

Python 3.1 解决方案：

>>> from collections import Counter
>>> x = [1,2,3,4,5,4,2,1,5]
>>> [value for value,count in Counter(x).items() if count == 1 ][0]
3
>>> 

• Paddy.

- Paddy3118

Answer 8

这并不符合“没有额外空间”的要求，但它会减少空间，除非数字按特定方式排序。

在Python中：

arr = get_weird_array()
hash = {}

for number in arr:
   if not number in hash:
     hash[number] = 1
   else:
     del hash[number]

for key in hash:
    print key

- Andrew Johnson

---

我认为你的意思是 del hash[number]。 - Seth

Answer 9

算法2：

1. 对数组进行排序。
2. 现在解析数组，如果两个连续的数字不相同，我们就得到了我们要找的数字。
3. 这样做不会使用额外的空间。

- Learner

---

问题在于这不是O(n)。排序是O(log n)。 - Glenn

排序的时间复杂度是 O(n log n)， 而不是 O(log n)。 - Steve Jessop

O(log n)比O(n)好太多了...可惜onbyone没有理解对。 - R. Martinho Fernandes

排序的时间复杂度为O(N)。比较排序的时间复杂度为O(n log n)，但是这里不需要使用比较排序。由于这些是数字，因此可以使用O(N)的原地排序算法，例如基数排序。 - SPWorley