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;
}
};