在一个数组中查找元素，其中每个元素都重复奇数次（但不止一次），只有一个元素出现一次

Question

在一个数组中查找元素，其中每个元素都重复奇数次（但不止一次），只有一个元素出现一次

25

你有一个数组，其中每个数字都出现了奇数次（但不止一次）。只有一个数字出现了一次。如何找到只出现一次的数字？

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

答案是9。

我考虑使用哈希表，然后只计算出现次数为1的元素。这似乎很简单，但我没有利用每个其他元素重复了奇数次这一事实。是否有更好的方法？

- shreyasva

1

如果9确实是答案，那么这个问题的措辞并不是很好。我认为9出现了奇数次（1次），1出现了奇数次（3次），3出现了奇数次（5次），6出现了奇数次（3次）。一个更有趣的问题是，一些数字重复了奇数次，而另一些数字重复了偶数次。 - Jacob Mattison

抱歉我误读了。问题可能有些遗漏了吗？也许这个想法是你必须使用固定大小的内存？但这仍然不是很有趣，而且据我所见也没有使用“奇数”。 - andrew cooke

1

这是一个链接，其中有奇数和偶数重复的更有趣版本：http://www.technicalinterviewquestions.net/2009/01/integer-array-odd-even-occurrences-find.html - Jacob Mattison

5个回答

21

对于所述问题，最有效的答案很可能是O(n)空间答案。另一方面，如果我们将问题缩小为“所有数字出现n次，除了只出现一次的数字”甚至“所有数字出现n的倍数次，除了只出现一次的数字”，那么对于任何n（显然大于1），都有一个相当直接的解决方案，只需要使用O(1)空间，即将每个数字拆分成位，然后计算每个位被打开的次数并将其模n。如果结果为1，则应在答案中将其打开。如果结果为0，则应将其关闭。（任何其他答案都表明问题的参数不满足）。如果我们考虑n为2的情况，我们可以看到使用异或恰好可以实现这一点（按位加法模2）。我们只是将事物概括为对于其他值的n进行按位加法模n。

顺便说一下，n=3的另一个答案实际上只是以复杂的方式进行按位加法，在其中存储每个位的2位计数。称为“ones”的int包含计数的ones位，称为“twos”的int包含计数的twos位。当计数达到3时，使用int not_threes将两个位都设置回零，因此计算比正常情况下（模4，因为位会绕过）少模3个位。理解他的代码最简单的方法是将其视为具有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次，我们只需将3改为5。或者我们可以对7、11、137、727或任何其他数字（包括偶数）做同样的事情。但是，我们可以使用它的任何因子，而不是使用实际数字，因此对于9，我们可以将其保留为3，对于偶数，我们可以使用2（因此只需使用异或）。

然而，在原始问题中，如果一个数字可以重复任意奇数次，则没有通用的基于位计数的解决方案。这是因为即使我们精确地计算位数而不使用模数，当我们查看特定位时，我们根本无法知道它出现了9次，是表示3 + 3 + 3还是1 + 3 + 5。如果它在三个不同的数字中被打开，每个数字都出现三次，那么它应该在我们的答案中关闭。如果它在出现一次的数字、出现三次的数字和出现五次的数字中被打开，那么它应该在我们的答案中打开。但是仅凭位数计数，我们无法知道这一点。

这就是为什么其他答案不具有普适性，处理特殊情况的聪明想法也不会实现：基于逐位查看事物以确定应该打开或关闭哪些位的任何方案都不具有普适性。鉴于此，我认为任何空间复杂度为O（1）的方案都无法适用于一般情况。可能有一些聪明的方案可以使用O（lg n）空间等等，但我对此表示怀疑。我认为O（n）空间方法可能是提出问题时可以做的最好的方法。我不能证明它，但目前我的直觉告诉我，我希望我至少已经说服了您，微调“偶数”技术是行不通的。

- Keith Irwin

1

我有关于你的代码的问题。如果数组是{1,2,2,2}，经过每个数字后，count[]将包含：1,0,0..(0将重复31次)-如果我理解正确，count[0]记录LSB是否已设置为1或3次。所以当我们到达最后一个for循环时，count[0]=1，所以答案是按位OR运算1，这将使答案=00..(31次)1。我的问题是，然后你左移答案，并在for循环中继续进行，所以最终答案将是：100..(31次)，这不会是答案的反转吗？我期望的是00..(31次)1（对于1）。如果有错，请纠正，谢谢。 - Jake

实际上，你甚至都不会得到那个结果。因为在最后一次循环中，在进行或运算之后发生移位时，我不小心将前面的1移走了，所以你只会得到00..（32次）。但是没错，它确实颠倒了一些东西。对此我感到抱歉，这就是我写代码而没有测试它的后果。第一个循环中也有几个错误，本来应该将所有内容初始化为0。现在已经全部修复了，感谢你的指出。 - Keith Irwin

2

我知道这个问题的背景是要找到一种高效或者性能良好的解决方案，但是我认为最简单易读的代码也是非常重要的，在大多数情况下它已经足够了。

那么这样怎么样：

var value = (new [] { 1, 6, 3, 1, 1, 6, 6, 9, 3, 3, 3, 3, })
    .ToLookup(x => x)
    .Where(xs => xs.Count() == 1)
    .First()
    .Key;

好老的LINQ。 :-)

- Enigmativity

0

Java，正确性100％，性能100％，任务得分100％

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.HashMap;

class Solution {

     /*Simple solution 
          Will be using HashMap(for performance) as Array, 
          only Key set is needed.
          Initially tried with ArryList but there was performance issue with
          that so switch to HashMap.
          Iterate over the given array and if item is there in key set         
          remove it(coz you found your pair) otherwise add as new Key.
          After full Iteration only one key will be there in the Map that is 
          your solution.
          In Short: If pair is found, remove it from Map's Key set,
          Last Key will be your solution
    */
    public int solution(int[] A) {

        //Map but used as Array
        final HashMap<Integer, Boolean> mapHave = new HashMap<>();

        //Iterate over given Array
        for (int nIdx = 0; nIdx < A.length; nIdx++) {

            //Current Item
            Integer nVal = A[nIdx];

            //Try to remove the current item, if item does not exists will
            //return null and if condition will be true
            if (mapHave.remove(nVal) == null) {
                //current item not found, add it
                mapHave.put(nVal, Boolean.TRUE);
            }
        }

        //There will be only one key remaining in the Map, that is
        //your solution
        return mapHave.keySet().iterator().next();
    }
}

- Sarveshwar Singh

你应该添加一些解释说明为什么这段代码可以工作 - 你也可以在代码本身中添加注释 - 在当前形式下，它没有提供任何解释，这可能有助于其他社区成员理解你是如何解决/回答问题的。 - ishmaelMakitla

@ishmaelMakitla 是的，谢谢你指出来。我正在修改方案并添加注释。如果您感觉需要进行更改，请回复我。 - Sarveshwar Singh

这不是O(n)，因为它使用了一个时间复杂度为O(log(n))的哈希表。 - Juan Vilar

0

使用C#测试得分100%

using System;
using System.Collections.Generic;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    public int solution(int[] A) {

        Dictionary<int, int> dic =new Dictionary<int, int>();

        foreach(int i in A)
        {
            if (dic.ContainsKey(i))
            {
                dic[i]=dic[i]+1;                
            }
            else
            {
                dic.Add(i, 1);                
            }
        }

        foreach(var d in dic)
        {
            if (d.Value%2==1)
            {
                 return d.Key;
            }
        }

        return -1;
    }
}

- Bashir Momen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- PengOne · Accepted Answer

我相信你仍然可以使用异或的基本思想以巧妙的方式解决这个问题。

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

算法:

这里的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，因此所有成对的元素都会消失，留下孤立的元素。如果我们在这里尝试同样的策略，我们会得到不同元素的异或结果，这不是我们想要的。

相反，上面的算法执行以下操作：

- ones是迄今为止仅出现一次的所有元素的异或 - twos是迄今为止出现两次的所有元素的异或

每次我们将x作为数组中的下一个元素时，有三种情况：

- 如果这是x第一次出现，则将其与ones进行异或 - 如果这是x第二次出现，则从ones中取出它（再次进行异或）并将其与twos进行异或 - 如果这是x第三次出现，则将其从ones和twos中取出。

因此，最终，ones将是仅一个元素的异或，即不重复的孤立元素。我们需要查看5行代码才能看到为什么这行得通：在x = A[i]之后的五行代码。

如果这是x第一次出现，则ones& x = ones，因此twos保持不变。行ones ^ = x;对x进行异或，如所述。因此，x恰好位于ones和twos中的一个，因此在最后三行中，ones和twos都没有发生任何事情。

如果这是x第二次出现，则ones已经有了x（通过上面的解释），因此现在行twos |= ones & x;使得twos也有了x。由于ones有x，所以行ones ^= x;从ones中除去了x（因为x^x=0）。再次，由于ones和twos中恰好有一个元素x，最后三行不会对其中任何一个进行修改。

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