540. Single Element in a Sorted Array

發表於 | 分類於

problem

solution

  • cheat
    1
    2
    int ret = 0;
    for(int a:nums) ret^=a;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        // 一定是奇數長度
        // 如果mid索引是偶數代表索引前面的數字應該都是兩兩一對，如果不是mid索引的值會與前一索引值相同，則落單的數必定在前面，反之相反。
        int l = 0, r = n-1;
        while(l<r){
            int mid = l +(r-l)/2;
            
            if (( mid % 2 == 1 && nums[mid] != nums[mid + 1]) || ( mid % 2 == 0 && nums[mid] == nums[mid + 1])) l = mid + 1;
            else r= mid;
            
            
        }
        return nums[l];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return nums[0];
        int l = 0 , r = n-1;
        while(l<r){
            int mid = l+ (r-l)/2;
            cout<<l<<" "<<r<<" "<<mid<<"\n";
            if(mid -1>= 0 && mid +1 <n && nums[mid]!=nums[mid-1] && nums[mid]!=nums[mid+1]) return nums[mid];
            if((mid+1)%2==0 && nums[mid-1] == nums[mid] ) l = mid+1;
            else if(mid+1 <n && (mid+1)%2==1 && nums[mid+1] == nums[mid]) l = mid+1;
            else r= mid-1;
        }
        return nums[l];
        
    }
};

analysis

  • time complexity O(logn)
  • space complexity O(1)