arrays - 在数组中查找一个元素，其中每个元素重复奇数次(但不止一次出现)，并且仅出现一次

您有一个数组，其中每个数字都重复奇数次(但不止一次出现)。恰好一个数字出现一次。您如何找到仅出现一次的号码？

e.g.: {1, 6, 3, 1, 1, 6, 6, 9, 3, 3, 3, 3}

答案是9。

我正在考虑拥有一个哈希表，然后只对计数为1的元素进行计数。
这似乎是微不足道的，并且我没有使用其他元素重复几次的事实。有没有更好的方法。

最佳答案

我相信您仍然可以使用XOR的基本思想来巧妙地解决此问题。

首先，让我们改变问题，以使一个数字出现一次，而所有其他数字出现三次。

算法:

此处A是长度为n的数组:

   int ones = 0;
   int twos = 0;
   int not_threes, x;

   for (int i=0; i<n; ++i) {
            x =  A[i];
            twos |= ones & x;
            ones ^= x;
            not_threes = ~(ones & twos);
            ones &= not_threes;
            twos &= not_threes;
   }

恰好发生一次的元素存储在ones中。这使用了O(n)时间和O(1)空间。

我相信我可以将这个想法扩展到问题的一般情况，但是也许你们中的一个可以更快地做到这一点，所以我将暂时保留它，并在何时以及是否可以推广该解决方案时对其进行编辑。

说明:

如果问题是这样的:“一个元素出现一次，所有其他元素出现偶数次”，那么解决方案将是对元素进行XOR。原因是x^x = 0，因此所有成对的元素都将消失，仅留下孤独的元素。如果我们在此处尝试相同的策略，那么我们将得到不同元素的XOR，这不是我们想要的。

而是，上述算法执行以下操作:

ones是到目前为止仅出现过一次的所有元素的XOR

twos是到目前为止已出现两次的所有元素的XOR

每次我们将x用作数组中的下一个元素时，会出现以下三种情况:

(如果这是首次出现x)，则将其异或为ones

(如果这是第二次出现x)，则将其从ones中取出(再次对其进行XOR处理)，然后异或为twos

(如果这是第三次出现x)，则将其从ones和twos中取出。

因此，最后，ones将只是一个元素的XOR，即不再重复的孤独元素。我们需要查看5行代码以了解其工作原理:x = A[i]之后的五行代码。

如果这是第一次x出现，那么ones&x=ones因此twos保持不变。要求将ones ^= x;行与x进行ones异或。因此x恰好在ones和twos之一中，因此在ones或twos的最后三行中什么都没有发生。

如果这是x的第二次出现，则ones已经具有x(通过上面的说明)，因此现在twos用twos |= ones & x;行获取它。另外，由于ones具有x，因此ones ^= x;行从x中删除了ones(因为x^x=0)。再说一遍，最后三行什么也不做，因为ones和twos中的确切一个现在具有x。

如果这是x第三次出现，则ones没有x，但twos有。因此，第一行让twos保留x，第二行将x添加到ones。现在，由于ones和twos都具有x，因此最后三行从这两者中都删除了x。

概括:

如果一些数字出现5次，则该算法仍然有效。这是因为第4次出现x，它既不在ones中也不在twos中。然后，前两行将x添加到ones而不是twos，而后三行则不执行任何操作。第五次出现x，它在ones中，但不在twos中。第一行将其添加到twos中，第二行将其从ones中删除，最后三行不执行任何操作。

问题是第6次出现x，它是从ones和twos提取的，因此它在第7次通过时被加回到ones。我正在尝试一种聪明的方法来防止这种情况，但是到目前为止，我还是空虚的。

关于arrays - 在数组中查找一个元素，其中每个元素重复奇数次(但不止一次出现)，并且仅出现一次，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7338070/