136 SingleNumber
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?
这个问题很经典，变体也多。
最容易想到的做法肯定是开一个HashMap存每个数字出现的次数。
但是要求是O(n)的复杂度，没有额外的空间开销。
其实自己想很难想到，看了题解之后大多数人的感觉是还有这种操作？
就是用一个0和每个元素取异或，一个数异或自己为0，所以出现两次的数异或之后为0，而出现一次的数则保留了下来。
看代码：
public int singleNumber(int[] nums) {
int i = 0;
for (int num : nums) {
i ^= num;
}
return i;
}
137 Single Number II
LeetCode很有意思，出了1之后可能还有2，3都是变体，难度会增加，有时候思路完全不一样。
Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
这个说实话也是很难想到的，但是还是基于的位运算。
给出discuss中第一名的答案：
public int singleNumber(int[] A) {
int ones = 0, twos = 0;
for(int i = 0; i < A.length; i++){
ones = (ones ^ A[i]) & ~twos;
twos = (twos ^ A[i]) & ~ones;
}
return ones;
}
这个解法斟酌一下，大致思路就是：
一个数出现第一次的时候存在ones中，出现第二次的时候存在twos中，出现第三次的时候在ones中被清0。所以最后保留的就是出现一次的数。
- Single Element in a Sorted Array
上面一题其实已经很枯燥了，不过这一题很有意思。
Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.
Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10
** Note** : Your solution should run in O(log n) time and O(1) space.
给出一个已经排序过的数组，除了一个数只出现了一次，其他的数都出现了两次。
其实用137题的写法也是可以的。
但是我们浪费了它已经排序过这个条件了。
再看看复杂度给的是O(lgn)
很容易想到的是二分。
public int singleNonDuplicate(int[] nums) {
int left = 0;
int right = nums.length / 2;
while (left < right) {
int mid = left + (right - left)/2;
if (nums[mid * 2] == nums[mid * 2 + 1]) {
left = mid+1;
}
else {
right = mid;
}
}
return nums[left * 2];
}
