在数组中查找元素,其中每个元素重复奇数次(但多于单次出现),并且只出现一次

Question

你有一个数组,其中每个数字重复奇数次(但超过单次出现).恰好一个数字出现一次.你怎么找到只出现一次的号码？

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

答案是9.

我正在考虑使用哈希表,然后只计算计数为1的元素.这似乎微不足道,我没有使用其他元素重复奇数次的事实.有没有更好的方法.

Answer 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)空间.

我相信我可以将这个想法扩展到问题的一般情况,但可能你们其中一个人可以更快地完成它,所以我现在就离开这个并编辑它,如果我可以概括解决方案.

说明:

如果问题是这样的:"一个元素出现一次,所有其他元素出现偶数次",那么解决方案就是对元素进行异或.原因是x^x = 0,所有配对的元素都会消失,只留下孤独的元素.如果我们在这里尝试相同的策略,我们将留下不同元素的XOR,这不是我们想要的.

相反,上面的算法执行以下操作:

• ones 是到目前为止只出现过一次的所有元素的XOR
• twos 是到目前为止两次出现的所有元素的XOR

每次我们x成为数组中的下一个元素时,有三种情况:

1. 如果这是第一次x出现,那就是XORedones
2. 如果这是第二次x出现,则将其从ones(通过再次XORing)中取出并进行异或twos
3. 如果这是第三次x出现,它将被取出ones并且twos.

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

如果这是第一次x出现,那么ones&x=ones这样twos保持不变.该线与所声称的ones ^= x;XOR x一致ones.因此x在恰好一个ones和twos,所以什么也没有发生在过去的三线两种ones或twos.

如果这是第二次x出现,那么ones已经x(通过上面的解释),所以现在twos得到它与线twos |= ones & x;.此外,由于oneshas x,该行将从(因为)中ones ^= x;删除.再次,最后三行自做的正好一个没有和现在有.xonesx^x=0onestwosx

如果这是第三次x出现,则ones没有x,但twos确实.所以第一线,让我们twos保持x与第二增加x至ones.现在,因为两者ones并twos有x,最后三行中删除x从两个.

概括:

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

问题是第6次x出现,它取自ones和twos,因此它被添加回ones第7次传球.我试图想出一个聪明的方法来防止这种情况,但到目前为止,我已经空了.

Answer 2

对于所述的问题,最有效的答案很可能是O(n)空间答案.另一方面,如果我们将问题缩小为"所有数字出现n次,除了只出现一次"或"甚至"所有数字出现n倍的倍数,除了只出现一次的那个"然后有一个相当简单的任何n(大于1,显然)的解决方案,它只占用O(1)空间,即将每个数字分成多个位,然后计算每个位被打开的次数并取模数n.如果结果为1,则应在答案中打开它.如果为0,则应关闭它.(任何其他答案显示问题的参数不成立).如果我们检查n为2的情况,我们可以看到使用XOR就是这样(按位加法模2).我们只是概括性地为n的其他值进行按位加法模n.

顺便说一下,这是n = 3的另一个答案,它实际上只是一种复杂的逐位加法方式,它为每个位存储一个2位计数.名为"ones"的int包含count的1位,而名为"twos"的int包含count的两位.int not_threes用于在计数达到3时将两个位都设置回零,从而计算模3的位而不是正常的位(由于位将环绕,因此将是模4).理解他的代码的最简单的方法是作为一个2位累加器,有一个额外的部分,使其工作模3.

因此,对于除了一个唯一编号之外所有数字出现3次的倍数的情况,我们可以为32位整数编写以下代码:

int findUnique(int A[], int size) {
  // First we set up a bit vector and initialize it to 0.
  int count[32];
  for (int j=0;j<32;j++) {
    count[j] = 0;
  }

  // Then we go through each number in the list.
  for (int i=0;i<size;i++) {
    int x = A[i];

    // And for each number we go through its bits one by one.
    for (int j=0;j<32;j++) {
      // We add the bit to the total.
      count[j] += x & 1;
      // And then we take it modulo 3.
      count[j] %= 3;
      x >>= 1;
    }
  }

  // Then we just have to reassemble the answer by putting together any
  // bits which didn't appear a multiple of 3 times.
  int answer = 0;
  for (int j=31;j>=0;j--) {
    answer <<= 1;
    if (count[j] == 1) {
      answer |= 1;
    }
  }

  return answer;
}

这段代码比其他答案略长(由于额外的循环,表面看起来更复杂,但它们每个都是恒定的时间),但希望更容易理解.显然,我们可以通过更密集地打包来减少内存空间,因为我们从来没有对计数中的任何数字使用超过两个.但我没有费心去做,因为它对渐近复杂性没有影响.

如果我们希望更改问题的参数,以便将数字重复5次,我们只需将3s更改为5s.或者我们也可以为7,11,137,727或任何其他数字(包括偶数)做同样的事情.但是不使用实际数字,我们可以使用它的任何因子,因此对于9,我们可以将其保留为3,对于偶数,我们可以使用2(因此只使用xor).

然而,对于原始问题,没有一般的基于比特计数的解决方案,其中数字可以重复任何奇数次.这是因为即使我们在不使用模数的情况下完全计算位数,当我们查看特定位时,我们根本无法知道它出现的9次是否代表3 + 3 + 3或1 + 3 + 5.如果是打开三个不同的数字,每个出现三次,然后在我们的答案中应该关闭它.如果它出现在一个出现一次的数字,一个出现三次的数字,一个出现五次的数字,那么它应该在我们的答案中打开.但只有位数,我们就不可能知道这一点.

这就是为什么另一个答案没有概括,并且处理特殊情况的聪明想法不会实现:任何基于逐位查看事物以确定应该打开或关闭哪些位的方案都不会一概而论.鉴于此,我认为任何占用空间O(1)的方案都不适用于一般情况.有可能有巧妙的方案使用O(lg n)空间等,但我会怀疑它.我认为O(n)空间方法可能是所提出的问题中可以做到的最好的方法.我无法证明这一点,但在这一点上,这是我的直觉告诉我的,我希望我至少让你相信对"偶数"技术的小调整不会削减它.