Question:
**
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
**
我一开始的思路很明显，用哈希表。
把数列的数字存入哈希表，然后当发现位置已经存了数字时，表示这个数字为 twice，于是我直接将该数字从哈希表移除。那么最后哈希表就只会剩下一个数字，他只出现了 once。 但是也会有问题哈。如果有个数字是 100000000，其他的都是很小的数字，那么就会浪费空间了。
上代码
public class Solution {
public int singleNumber(int[] nums) {
HashSet<Integer> set = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i]))
set.remove(nums[i]);
else
set.add(nums[i]);
}
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i]))
return nums[i];
}
return 0;
}
}
由系统分析可知，运算时间比较长。
于是我再次看评论，大神们是怎么做的。于是乎看到了一个，
惊为天人的方法！
我们都知道异或操作，相同的就会为0。然后存在这么一个等式：
**
A XOR B XOR C = A XOR C XOR B = B XOR C XOR A = B XOR A XOR C....
**
也就是说，异或操作遵守交换律。
那么假想下，数组里这么多个数，异或，可以把出现两次的数排在前面，只出现一次的数（唯一一个）排在最后。那么前面的异或结果都是0，直到最后，结果为这个只出现了一次的数。
于是我又拿Java重写了下这个方法。
上代码
public class Solution {
public int singleNumber(int[] nums) {
int s = 0;
for (int i = 0; i < nums.length; i++)
s ^= nums[i];
return s;
}
}
额，核心就四行代码，算法复杂度为 O(N),基本没有用什么空间。然后看系统测的评价
可以看到时间快了，而且内存肯定也少了。
但是，还不够快！
为什么，因为Java毕竟是建立在JVM上的，所以不能直接控制底层。那么，
用C重写吧。也许是今天兴致好，我又重写了C，或者说，比较容易重写吧。
上代码
int singleNumber(int* nums, int numsSize) {
int s = 0;
int i;
for (i = 0; i < numsSize; i++)
s ^= nums[i];
return s;
}
然后看系统的评价
额，速度一下子上升到了 15ms。。。这就是C语言，这就是指针的效率啊。。。
**
总结：
这次作业还是比较简单的。收获如下吧：
当有一大堆重复数字时，如果他们的类型同意，比如 integer。 那么就可以用异或操作来除去重复的数字，当然，只限于该题的情况。只不过是一种很好的思路。
这叫做， Bit Manipulation.
还有，C果然比Java快好多。。。第一次见识到指针的效率！
**
这次的题目也还不是很带劲。今天不做啦，明天继续。
Good luck, Richardo!
My code:
public class Solution {
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
int curr = nums[0];
for (int i = 1; i < nums.length; i++) {
curr = (curr ^ nums[i]);
}
return curr;
}
}
解法熟记在心了。。。
Anyway, Good luck, Richardo!
这道题目一直记得解法。。。很巧妙。做法类似，不写了。
Anyway, Good luck, Richardo! - 08/05/2016
