查找数组中没有对的数字

我遇到了一小段代码的问题，这些代码在一个随机大小的数组中，随机数对，除了没有对的代码。

我需要找到没有配对的号码。

arLength是数组的长度。 但我实际上匹配对，并找到没有对的那个..

for (int i = 0; i <= arLength; i++) { // go through the array one by one.. var number = nArray[i]; // now search through the array for a match. for (int e = 0; e <= arLength; e++) { if (e != i) { } } } 

我也试过这个：

 var findValue = nArray.Distinct(); 

我一直在寻找，但到目前为止，我还没有找到一种方法。

这段代码是生成数组的代码，但这个问题与代码的这一部分无关，只是为了清楚起见。

 Random num = new Random(); int check = CheckIfOdd(num.Next(1, 1000000)); int counter = 1; while (check <= 0) { if (check % 2 == 0) { check = CheckIfOdd(num.Next(1, 1000000)); ; } counter++; } int[] nArray = new int[check]; int arLength = 0; //generate arrays with pairs of numbers, and one number which does not pair. for (int i = 0; i < check; i++) { arLength = nArray.Length; if (arLength == i + 1) { nArray[i] = i + 1; } else { nArray[i] = i; nArray[i + 1] = i; } i++; } 

Answer 1

Distict将为您提供具有不同值的数组。 它找不到你需要的价值。

您可以使用GroupBy并选择Count modulo 2等于1的值。

 var noPairs = nArray.GroupBy(i => i) .Where(g => g.Count() % 2 == 1) .Select(g=> g.Key); 

Answer 2

您可以使用bitwise符^来完成它，复杂度为O(n) 。

理论

operator ^ aka xor有下表：

因此，假设您只有一个没有对的数字，所有对都将被简化，因为它们是相同的。

 var element = nArray[0]; for(int i = 1; i < arLength; i++) { element = element ^ nArray[i]; } 

最后，变量element将是没有对的数字。

Answer 3

您可以使用字典来存储数组中每个值的出现次数。 要查找不带对的值，请查找小于2的（单个）出现次数。

 using System.Linq; int[] data = new[] {1, 2, 3, 4, 5, 3, 2, 4, 1}; // key is the number, value is its count var numberCounts = new Dictionary(); foreach (var number in data) { if (numberCounts.ContainsKey(number)) { numberCounts[number]++; } else { numberCounts.Add(number, 1); } } var noPair = numberCounts.Single(kvp => kvp.Value < 2); Console.WriteLine(noPair.Key); 

时间复杂度为O（n），因为您只遍历数组一次，然后遍历字典一次。 同一个字典也可用于查找三元组等。

.NET小提琴

Answer 4

一种简单快捷的方法是使用频率表。 保留一个字典，其中包含您的数字和值，以及您找到它的次数。 这样，您只需运行一次数组。

您的示例也应该适用于某些更改。 如果你有一个大arrays会慢很多。

  for (int i = 0; i <= arLength; i++) { bool hasMatch = false; for (int e = 0; e <= arLength; e++) { if (nArray[e] == nArray[i])//Compare the element, not the index. { hasMatch = true; } } //if hasMatch == false, you found your item. } 

Answer 5

你所要做的就是Xor所有的数字：

  int result = nArray.Aggregate((s, a) => s ^ a); 

所有具有对的项目将抵消： a ^ a == 0并且您将具有distinc项目： 0 ^ 0 ^ ...^ 0 ^ distinct ^ 0 ^ ... ^0 == distinct

Answer 6

因为你在评论中提到你喜欢简短而简单，那么如何摆脱你的大部分其他代码呢？

 var total = new Random().Next(500000) * 2 + 1; var myArray = new int[total]; for (var i = 1; i < total; i+=2) { myArray[i] = i; myArray[i -1] = i; } myArray[total - 1] = total; 

然后确实使用Linq来获得你想要的东西。 这是一个细微的变化，返回数组中项目的键 ：

 var key = myArray.GroupBy(t => t).FirstOrDefault(g=>g.Count()==1)?.Key;