如何在数组中找到两个不成对的元素？

Question

您有一个包含 n=2k+2 个元素的数组，其中 2 个元素未配对。 8 元素数组的示例：1 2 3 47 3 1 2 0。“47”和“0”在数组中没有配对。如果我的数组中只有 1 个元素没有配对，我可以使用 XOR 解决这个问题。但我有两个不成对的元素！我能做些什么？解决方案可能是 O(n) 时间性能和 O(1) 额外内存。

Answer 1

一些提示...

需要 2 次通过。首先，遍历列表并将所有元素异或在一起。看看你会得到什么。从那里继续。

编辑：关于第一遍结果的关键观察应该是它显示了 2 个不成对元素不同的位集。

Answer 2

使用 INT_MAX/8 字节内存。走阵。将每个值对应的位与 1 进行异或。如果有 0 或 2 个实例，则该位最终为 0。如果只有 1 个实例，则将其设置。 O(1) 内存，O(N) 时间。

Answer 3

1. 扫描数组并将每个数字和计数放入哈希中。
2. 重新扫描并找出count=1的项目。

这是 O(n)。

Answer 4

你可以试试这个。这将需要 O(n) 时间

        int xor = arr[0];
        int set_bit_no;
        int i;
        int x = 0; //First unpair number
        int y = 0; //second unpair number
        for (i = 1; i < n; i++)
            xor ^= arr[i];

        set_bit_no = xor & ~(xor-1);//Get the rightmost set bit in set_bit_no
        for (i = 0; i < n; i++)
        {
            if (arr[i] & set_bit_no) {
                //XOR of first set 
                x = x ^ arr[i];
            }
            else
            {
                //XOR of second set
                y = y ^ arr[i];
            }
        }

解释...
arr[] = {2, 4, 7, 9, 2, 4}
1) 获取所有元素的异或。
异或 = 2^4^7^9^2^4 = 14 (1110)
2) 获取一个只有一位异或的数字。
由于我们可以轻松获得最右边的设置位，因此让我们使用它。
set_bit_no = 异或 & ~(xor-1) = (1110) & 〜（1101）= 0010
现在 set_bit_no 将仅设置为异或的最右边设置位。
3）现在将元素分为两个集合并进行异或
每个集合中的元素，我们得到不重复的
要素 7 和 9。