6

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

4

4 回答 4

8

一些提示...

需要2次通过。首先，遍历列表并对所有元素进行异或。看看你得到了什么。从那里继续。

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

于 2012-02-02T16:05:47.950 回答
1
  1. 扫描数组并将每个数字和计数放入哈希中。
  2. 重新扫描并找出 count=1 的项目。

这是 O(n)。

于 2012-02-02T20:21:37.673 回答
1

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

于 2012-02-02T16:02:32.913 回答
0

你可以试试这个。它需要 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) 得到所有元素的异或。xor = 2^4^7^9^2^4 = 14 (1110) 2) 得到一个只有一组异或的数字。
因为我们可以很容易地得到最右边的设置位，所以让我们使用它。set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010 现在 set_bit_no 将只设置为 xor 的最右边的设置位。3) 现在将元素分成两组，并对
每组元素进行异或，得到不重复的元素 7 和 9。

于 2017-04-25T11:48:38.880 回答