Leetcode Valentine's Day Special - looking for a single dog

subject

Topic link

Topic explanation

This question should have been simple , Is a simple XOR law , But the title requires the use of O(logn) Time complexity , O(1) Spatial complexity , And if direct XOR , Can only be O(n) Time complexity of .

So how to do it ？

This question has two paragraphs , What is dyadic , That is, there can be a dividing point to divide the characteristics into two . Because the data is ordered , So elements with two numbers will be next to each other , And in single af The subscripts of continuous elements on the left will have the following rules ： In two adjacent identical elements , The subscript of the first element will be even , The second is odd . The subscripts of continuous elements on the right will have the following rules ： In two adjacent identical elements , The first element subscript is an odd number , The second is even .

According to the above two paragraphs, you can quickly build a binary version of the code ！

Solution code

The binary version is not simplified

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

Simplified binary version

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