Java 如何找到数组中唯一没有出现两次的数字
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/29333689/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to find the only number in an array that doesn't occur twice
提问by Adam
The following is taken from a job interview:
以下内容来自求职面试：
In a given array, which contains integers, each number repeats itself once except for one, which doesn't repeat. Write a function that finds the number that doesn't repeat.
在包含整数的给定数组中，除了一个不重复之外，每个数字都会重复一次。编写一个函数来查找不重复的数字。
I thought about using an HashSet, but it might complicate everything...
我想过使用 HashSet，但它可能会使一切复杂化......
Any ideas of a simple solution?
任何简单解决方案的想法？
采纳答案by dhokas
You can define an integer "result" initialized to 0, and then you do some bitwise operations by applying a XOR logic to all elements in your array.
您可以定义一个初始化为 0 的整数“结果”，然后通过对数组中的所有元素应用 XOR 逻辑来执行一些按位运算。
At the end, "result" will be equal to the only element that appears only one time.
最后，“result”将等于仅出现一次的唯一元素。
result = 0
for i in array:
result ^= i
return result
http://en.wikipedia.org/wiki/Bitwise_operation#XOR
http://en.wikipedia.org/wiki/Bitwise_operation#XOR
For instance, if your array contains the elements [3, 4, 5, 3, 4], the algorithm will return
例如，如果您的数组包含元素 [3, 4, 5, 3, 4]，则算法将返回
3 ^ 4 ^ 5 ^ 3 ^ 4
3^4^5^3^4
But the XOR operator ^ is associative and commutative, so the result will be also equal to:
但是 XOR 运算符 ^ 是关联和可交换的，因此结果也将等于：
(3 ^ 3) ^ (4 ^ 4) ^ 5
(3^3)^(4^4)^5
Since i ^ i = 0 for any integer i, and i ^ 0 = i, you have
因为对于任何整数 i，i ^ i = 0，并且 i ^ 0 = i，你有
(3 ^ 3) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 5 = 5
(3 ^ 3) ^ (4 ^ 4) ^ 5 = 0 ^ 0 ^ 5 = 5
回答by Paul Boddington
I've seen this question before. It's a trick. Assuming all the repeated numbers appear exactly twice you do this:
我以前看过这个问题。这是一个伎俩。假设所有重复的数字恰好出现两次，您可以这样做：
int result = 0;
for (int a : arr)
result ^= a;
回答by KSFT
Here's a slightly less obfuscated way to do it:
这是一种稍微不那么混淆的方法：
List list = Arrays.asList(a);
int result;
for(int i:a)
{
if(list.indexOf(i)==list.lastIndexOf(i))
{
result = i;
break;
}
}
resultwill contain the non-repeated value.
result将包含非重复值。
回答by icza
The best answer is already given (XOR-ing the elements), this is to provide an alternative, more general way.
最好的答案已经给出（对元素进行异或运算），这是提供一种替代的、更通用的方法。
If the input array would be sorted (we can make it sorted), we could simply iterate over the elements in pairs (stepping by 2) and if the elements of the "pair" are different, we're done:
如果输入数组将被排序（我们可以对其进行排序），我们可以简单地迭代成对的元素（步长为 2），如果“对”的元素不同，我们就完成了：
public static int findSingle(int[] arr) {
Arrays.sort(arr);
for (int i = 0, max = arr.length - 1; i < max; i += 2)
if (arr[i] != arr[i + 1])
return arr[i];
return arr[arr.length - 1]; // Single element is the last
}
Note:This solution sorts the input array; if this is unwanted or not allowed, it can be cloned first:
注意：此解决方案对输入数组进行排序；如果这是不需要的或不允许的，可以先克隆它：
arr = arr.clone();
If input array is sorted, the Arrays.sort(arr)call can be left out of course.
如果输入数组已排序，则Arrays.sort(arr)当然可以省略调用。
Generalization
概括
The advantage of this solution is that it can be applied to all types which are comparable and therefore can be sorted (types which implement Comparable), for example Stringor Date. The XORsolution is limited to numbers only.
这种解决方案的优点是它可以应用于所有可比较的类型，因此可以排序（实现 的类型Comparable），例如Stringor Date。该XOR解决方案仅限于数字。
Here is a slightly modified version which takes an input array of any element type which is comparable:
这是一个稍微修改的版本，它采用任何可比较的元素类型的输入数组：
public static <E extends Comparable<E>> E findSingle(E[] arr) {
Arrays.sort(arr);
for (int i = 0, max = arr.length - 1; i < max; i += 2)
if (arr[i].compareTo(arr[i + 1]) != 0)
return arr[i];
return arr[arr.length - 1]; // Single element is the last
}
Note: In most cases you could also use arr[i].equals(arr[i + 1])to compare elements instead of using Comparable.compareTo(). For details read the linked javadoc. Quoting the relevant part:
注意：在大多数情况下，您还可以使用arr[i].equals(arr[i + 1])比较元素而不是使用Comparable.compareTo(). 有关详细信息，请阅读链接的 javadoc。引用相关部分：
It is strongly recommended, but notstrictly required that
(x.compareTo(y)==0) == (x.equals(y)). Generally speaking, any class that implements theComparableinterface and violates this condition should clearly indicate this fact. The recommended language is "Note: this class has a natural ordering that is inconsistent with equals."
强烈推荐，但不严格要求
(x.compareTo(y)==0) == (x.equals(y))。一般而言，任何实现Comparable接口并违反此条件的类都应该清楚地表明这一事实。推荐的语言是“注意：这个类有一个与 equals 不一致的自然顺序。”
Now you can call this with a String[]for example:
现在你可以用一个String[]例子来调用它：
System.out.println(findSingle(new String[] { "1", "2", "3", "1", "3" }));
Output:
输出：
2
Final notes:
最后说明：
Starting from the problem statement it is not checked whether there are more than 2 occurrences of the elements, and neither is whether the array length is odd. Also the second example doesn't check for nullvalues, these are to be added if necessary.
从问题陈述开始，不检查元素是否出现超过 2 次，也不检查数组长度是否为奇数。此外，第二个示例不检查null值，如有必要，将添加这些值。
回答by user3078523
Yet another "ordinary" solution (in Java):
另一个“普通”解决方案（在 Java 中）：
public static int findSingle(int[] array) {
Set<Integer> set = new HashSet<Integer>();
for (int item : array) {
if (!set.remove(item)) {
set.add(item);
}
}
assert set.size() == 1;
return set.iterator().next();
}
In my opinion the solution with XOR is kind of beautiful.
在我看来，XOR 的解决方案有点漂亮。
This one is not as fast as XOR but usage of HashSet makes it close to O(n). And it is certainly more readable.
这个没有 XOR 快，但是 HashSet 的使用使它接近 O(n)。它当然更具可读性。
