写这篇文章的原因就是因为这道题花费了我一上午的时间，自己的理解能力真的是太渣了，原题连接请点击这里。
1 题目要求
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.
翻译过来就是说，有一个数组，这里面有很多数字是成对出现的，只有一个数字出现了一次，找到只出现了一次的数字。
注意限制了时间复杂度。
2 一些思路
因为限制了时间复杂度，一时没有想到好的解决方案（表示我从来不记每个算法的时间复杂度，除了几个排序的）。百度了下，O(log n)的算法，有三个，二分查找，欧几里得算法（说白了就是求两个数的最大公约数，不过叫欧几里得逼格比较高），计算一个整数的幂。这道题用到了二分查找。
二分查找的基本原理在此不多解释，注意一点，mid的奇偶对这个题有很大的影响，这也是我一直困惑的一个点。
序号 0 1 2 3 4 5 6
数组 X X X X X X X
此时left = 0, right = 6, mid = left + parseInt((right - left) / 2) = 3
mid两端都是奇数个值
当nums[mid] == nums[mid+1]时，右侧此时就会剩下偶数个值，因此只出现一次的数字不会出现在右侧
反之，nums[mid] == nums[mid-1]时，左侧就会剩下偶数个值，因此只出现一次的数字不会出现在左侧
序号 0 1 2 3 4
数组 X X X X X
此时left = 0, right = 4, mid = left + parseInt((right - left) / 2) = 2
mid两端都是偶数个值
当nums[mid] == nums[mid+1]时，右侧此时剩下奇数个值，因此只出现一次的数一定会在右侧
反之，nums[mid] == nums[mid-1]时，左侧剩下奇数个值，因此只出现一次的数一定会在左侧
明白了这一点，就可以写代码了。
var singleNonDuplicate = function(nums) {
var left = 0,right = nums.length - 1;
while(left < right){
var mid = left + parseInt((right - left)/2);
if(nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1]){
return nums[mid];
}else if((mid % 2 == 0 && nums[mid] == nums[mid+1]) || (mid % 2 == 1 && nums[mid] == nums[mid-1])){
left = mid + 1;
}else{
right = mid - 1;
}
}
return nums[left];
};
如果这道题不限制时间复杂度，还有一些很有意思的做法。
- 运用indexOf和lastIndexOf（只出现一次的数字indexOf和lastIndexOf的值一样）
var singleNonDuplicate = function(nums) {
var len = nums.length,i;
for(i=0;i<len;i++){
if(nums.indexOf(nums[i]) == nums.lastIndexOf(nums[i])){
return nums[i];
}
}
}
- 运用map集合
var singleNonDuplicate = function(nums) {
var len = nums.length,i,map = new Map();
for(i=0;i<len;i++){
map.has(nums[i]) == false ? map.set(nums[i],1) : map.set(nums[i],map.get(nums[i])+1);
}
for(let key of map.keys()){
if(map.get(key) == 1){
return key;
}
}
}
- 运用位运算符取异或（这个方法真的巧妙 反正我是没想到）
var singleNonDuplicate = function(nums) {
var len = nums.length,i,num = 0;
for(i=0;i<len;i++){
num ^= nums[i];
}
return num;
}
3 总结
这道题看起来不难，值得反思的地方还是有一些的，其次以后刷题的时候要注意位运算符这个点，往往能起到令人意想不到的效果。
码字不易，请尊重作者版权，转载注明出处。
By BeLLESS 2017.7.10 14:02
