在数组中查找奇数项(没有对)的算法？

Question

可能重复:
在列表中查找单个数字

给定一个整数数组的好算法,除了其中一个整数出现偶数次之外,找到一个出现奇数次的整数.

或许像二进制搜索一样的东西,比如2个n/2大小的小数组的所有元素,比较递归找出来？

编辑:

这个XOR算法实际上是假设{1,1,4,4,7,7,5,8,8,9,9}吗？我的输入也可以是randmon - {1,4,1,8,9,5,4,5,9,8}.那么这种情况下逻辑会发生变化吗？

Answer 1

XOR所有数组元素.结果将是重复奇数次的元素.

Answer 2

XOR元素.因为每个数字出现一次,表示它的位将来回切换,并且您将只留下代表唯一未出现两次的数字的位.

[TestMethod]
public void SumOfPairs()
{
    var nums = new[] { 1, 1, 4, 4, 7, 7, 5, 8, 8, 12, 12 };
    int i = 0;
    foreach (var num in nums)
    {
        i ^= num;
    }

    Assert.AreEqual(5, i);
}

请注意,除非您指定的确切条件存在,否则这不起作用.