leetcode情人节特辑——寻找单身狗
目录
题目
题目详解
这题本应是简单题，就是简单的异或规律，但是题目要求使用 O(logn) 时间复杂度， O(1) 空间复杂度，而如果直接异或，只会是 O(n) 的时间复杂度。
那么该如何去做呢？
这题有二段性，什么叫二段性呢，就是能有一个分界点把特性一分为二。比如此题由于数据是有序的，所以数量为两个的元素会挨在一起，而且在 单身狗 左边连续的元素下标会有以下规律：两个相邻的相同元素中，第一个元素下标会是偶数，第二个是奇数。右边的连续元素下标会有以下规律：两个相邻的相同元素中，第一个元素下标是奇数，第二个是偶数。
根据以上二段性可很快构建出二分版本的代码！
解题代码
未简化二分版本
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int l=0,r=nums.size()-1;
int maxr = r;
int mid;
while(l<r){
mid = (l+r)/2;
if(mid<maxr&&nums[mid+1]==nums[mid]){
if(mid%2==0){
l = mid+2;
}else{
r = mid;
}
}else if(mid>0&&nums[mid-1]==nums[mid]){
if((mid-1)%2==0){
l = mid+1;
}else{
r = mid;
}
}else{
return nums[mid];
}
}
return nums[l];
}
};
简化的二分版本
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int low = 0, high = nums.size() - 1;
while (low < high) {
int mid = (high - low) / 2 + low;
if (nums[mid] == nums[mid ^ 1]) {
low = mid + 1;
} else {
high = mid;
}
}
return nums[low];
}
};