540. Single Element in a Sorted

写这篇文章的原因就是因为这道题花费了我一上午的时间，自己的理解能力真的是太渣了，原题连接请点击这里。

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