在数组中查找不成对的数字

Question

我有一个数组,其中除了一个重复所有元素:

int[] a={2,6,6,2,4,1,4};

如何找到未配对的元素整数？

Answer 1

您可以采取以下几种方法:

• 方法1 - O(n log n):对数组进行排序.然后,在时间(遍历排序后的数组中,两个中的元素i=0,i=2等等).何时a[i]和a[i+1]不平等 - 或何时i+1 == a.length- 你知道这a[i]是不成对的.
• 方法2 - O(n ²):迭代元素.对于每个元素a[i],迭代的元素(在嵌套循环),看看是否曾经发生认为a[i] == a[j]同时i != j.如果没有,则a[i]取消配对.
• 方法3 - O(米),其中米是最大和最小元素之间的差(注意,米是Ω(Ñ)):遍历元素,找到最大和最小值MIN和MAX.创建一个int[] b = new int[MAX-MIN+1].再次迭代元素,b[a[i]-MIN]为每个元素递增.然后迭代b; 当你发现时b[j]==1,j是不成对的.

注意:您使用术语"元素整数",但这不是一个真正的术语.以上假设您的意思是"整数值元素".如果您实际上是指"元素索引 ",则只能使用方法2而无需修改.方法3需要进行一些调整,方法1需要进行大量调整.(当然,一旦你发现只出现一次的值,你可以再次遍历数组以找到该值的索引 - 前提是你仍然拥有原始的数组顺序.)

编辑添加:我不知道我之前是如何错过的 - 我想我在编写Java时不习惯按位运算 - 但最好的解决方案实际上是:

• 方法4 - O(n):计算^数组所有元素的按位XOR .这是不成对的元素.你看,XOR是可交换的和联想的,所以2^6^6^2^4^1^4是相同的1^(2^2)^(4^4)^(6^6); 并且x^x总是0如此,所以对总是取消其他的.你可以写:

  int result = 0;
  for(int i : a)
      result ^= i;
  

  计算不成对的元素.(要获取未配对元素的索引,您需要再次遍历数组,寻找result.)