给定一个整数数组，除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素。
备注：
你的算法应该是一个线性时间复杂度。 你可以不用额外空间来实现它吗？
分析：
这是一道著名的面试题，题意明显，所有的元素都是成对出现的，只有1个元素是单身。
解法一：
很容易想到的解决办法就是把数组排序，相同的元素会前后挨着，正常情况下脚标为0和1的两个元素相同，2和3两个元素相同，直到那个单身的元素出现才会扰乱这个局面，就这样当出现两个元素不相同的时候，前一个元素就是要找的单身元素。
这种解法虽然可以找出单身元素，但是要使用排序，排序的时间复杂度是O(nlogn)，不是线性时间复杂度（O(n)），不符合平台的要求。
public int singleNumber(int[] nums) {
if (nums.length == 0) {
return -1;
}
if (nums.length == 1) {
return nums[0];
}
Arrays.sort(nums);
for (int i = 0; i < nums.length; i += 2) {
if (i == nums.length - 1) {
return nums[i];
}
if (nums[i] != nums[i + 1]) {
return nums[i];
}
}
return 0;
}
解法二：
第二种解法可以完美的解决这个问题。使用的是异或的方法。
先简单的介绍一下异或。异或是二元运算符，必须要有两个元素参与运算。
异或简单的说：两者的值不同返回true，两者的值相同返回false。
真值表.png
异或的特性：
1.恒定律：A ^ 0 = A
2.归零率：A ^ A = 0
3.交换律：A ^ B = B ^ A
4.结合律：(A ^ B) ^ C = A ^ (B ^ C)
异或可以做的事情：
异或可以快速比较两个值是否相等 a ^ b == 0，效率非常高，比 a - b == 0 高很多。
异或还能在不定义临时变量的情况下，交换两个值（经典题目）
a = a ^ b
b = a ^ b // a ^ b ^ b = a ^ 0 = a
a = a ^ b // a ^ b ^ a = b ^ 0 = b
好了，现在利用学习的异或知识，来分析一下这道题。
假设所有的数组为：abcbcda
a ^ b ^ c ^ b ^ c ^ d ^ a
= a ^ a ^ b ^ b ^ c ^ c ^ d
= 0 ^ 0 ^ 0 ^ d
= d
很神奇是不是？这个的时间复杂度为O(n)，是线性的，空间复杂度是O(1)
Java代码如下：
public int singleNumber(int[] nums) {
if (nums.length == 0) {
return -1;
}
if (nums.length == 0) {
return nums[0];
}
int result = 0;
for (int i = 0; i < nums.length; i++) {
result = result ^ nums[i];
}
return result;
}
网友评论