540. Single Element in a Sorted Array

Single Element in a Sorted Array – LeetCode

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Follow up: Your solution should run in O(log n) time and O(1) space.

从题目中可以看出, 这是一个有序数组(不是有序的也没关系, 可以先排序), 时间复杂度在O(log n); 看到时间复杂度的要求, 很容易就能想到这题可以用二分查找(Binary Search).

首先找到中位数, 如果中位数刚好就是答案, 那么中位数肯定和前后两个元素都不相等; 如果中位数不是答案, 那么中位数必定和前面或在后面一个元素相同.

那么,在找出来相同元素之后, 到底是该取左半区域继续作二分查找, 还是取右半区域呢?

这里有一点需要注意, 中位数划分出来的左右两个区域, 可能包含偶数个元素, 也可能包含奇数个元素, 两种情况下需要作不同的处理. (我在最开始解题的时候并没有考虑到, 导致testcase一直fail.)

当中位数为奇数时, 说明划分出来的两个区域包含的元素也为奇数, 此时, 如果中位数和左边的元素相同, 则说明答案应该在右边的区域, 取右边区域继续作二分查找即可, 反之亦然.

相反, 当中位数为偶数时, 说明划分出来的两个区域包含的元素也为偶数, 此时, 如果中位数和左边的元素相同, 由于减去该相同元素之后剩余的元素个数为奇数, 则说明答案应该在左边区域, 应当取左边区域继续作二分查找即可, 反之亦然. 当然, 在取左边或在右边区域的时候需要注意去掉和中位数相同的元素, 保证继续作二分查找的区域元素个数为奇数.

另外, 在作二分查找之前, 可以对一些特殊情况(比如答案在第一位或在最后一位的情况)提前作处理, 保证在后面的处理过程中不会出现越界的错误.

以下为解体答案:

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        if (nums[0] != nums[1]) return nums[0];
        int n = nums.size();
        if (nums[n -1] != nums[n - 2]) return nums[n - 1];

        int l = 0, h = n, m;
        while (l < h) {
            m = (l + h) / 2;
            if (m % 2) {              
                if (nums[m] == nums[m + 1])  { 
                    if (--m == l) return nums[l];
                    h = m;
                }  else if (nums[m] == nums[m - 1]) { 
                    if (++m == h) return nums[h];
                    l = m; 
                } else {return nums[m];}  
            } else {                
                if (nums[m] == nums[m - 1])  { 
                    if (--m == l) return nums[h];
                    h = m - 1;
                }  else if (nums[m] == nums[m + 1]) { 
                    if (++m == h) return nums[l];
                    l = m + 1; 
                } else {return nums[m];}
            }
        }
        return nums[l];
    }
};

在提交之后, 查看了别人内存使用率最低的解法, 瞬间惊为天人!

对数组中的所有元素依次作异或运算, 最终结果即为答案.

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int x(0);
        for(auto& i : nums)
            x ^= i;
        return x;
    }
};