Leetcode（540）—— A single element in an ordered array

subject

Give you an ordered array of integers only , Each of these elements will appear twice , Only one number will appear once .

Please find and return the number that only appears once .

The solution you design must meet $O(\log n)$ Time complexity and $O(1)$ Spatial complexity .

Example 1：

Input : nums = [1,1,2,3,3,4,4,8,8]
Output : 2

Example 2：

Input : nums = [3,3,7,7,10,11,11]
Output : 10

Tips :

• $1$ <= nums.length <= $10^5$
• $0$ <= nums[i] <= $10^5$

Answer key

Method 1 ： Binary search of full array

Ideas

​​   Because the given array is ordered And Regular elements always appear in pairs , So if you don't consider “ special ” Of a single element , We have a conclusion ： The subscript corresponding to the first of the paired elements must be even , The subscript corresponding to the second of the paired elements must be odd .
​​   then Then consider the case where there is a single element , If the subscript of a single element is $x$, So subscript $x$ Before （ On the left ） The position of still satisfies the above conclusion , And subscripts $x$ after （ On the right ） Due to $x$ Insertion , Cause the conclusion to flip .

​​   Suppose that the element that appears only once is in the subscript $x$, Because every other element appears twice , So subscript $x$ There are even elements on the left and right of , The length of the array is odd .

​​   Because arrays are ordered , Therefore, the same elements in the array must be adjacent . For subscripts $x$ The subscript on the left $y$, If $\text{nums}[y]=\text{nums}[y+1]$, be $y$ It must be an even number ; For subscripts $x$ The subscript on the right $z$, If $\text{nums}[z]=\text{nums}[z+1]$, be $z$ It must be odd . Because of subscript $x$ Is the boundary between the parity of the starting subscript of the same element , Therefore, we can use the binary search method to find the subscript $x$.

At the beginning , The left bound of binary search is $0$, The right boundary is the maximum subscript of the array . Take the average value of the left and right boundaries each time $\text{mid}$ As a subscript to be judged , according to $\text{mid}$ The parity of determines the comparison with the adjacent elements on the left or right ：

• If $\text{mid}$ It's even , Then compare $\text{nums}[\text{mid}]$ and $\text{nums}[\text{mid}+1]$ Whether it is equal or not ;
• If $\text{mid}$ Is odd , Then compare $\text{nums}[\text{mid}-1]$ and $\text{nums}[\text{mid}]$ Whether it is equal or not .

If the result of the above comparison of adjacent elements is equal , be $\text{mid}<x$, Adjust the left border , otherwise $\text{mid}\ge x$, Adjust the right border . After adjusting the boundary, continue the binary search , Until the subscript is determined $x$ Value . Get the subscript $x$ After the value of ,$\text{nums}[x]$ That is, the element that appears only once .

details （ Tips ）—— You don't have to judge $\text{mid}$ Parity

Using the properties of bitwise XOR , You can get $\text{mid}$ And adjacent numbers , among $\oplus$ Is a bitwise XOR operator ：

• When $\text{mid}$ When it's even ,$\text{mid}+1=\text{mid}\oplus 1$;
• When $\text{mid}$ It's an odd number ,$\text{mid}-1=\text{mid}\oplus 1$.

So in the process of binary search , You don't have to judge $\text{mid}$ Parity ,$\text{mid}$ and $\text{mid}\oplus 1$ That is, the two subscripts of each element to be compared .

because $0\oplus 1$ As the result of the $1$ , So don't worry that the left side will cross the border . Again because $mid=(l+r)/2$ therefore $mid$ The value of is rounded down , There will be no right access array out of bounds .

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    int singleNonDuplicate(vector<int>& nums) {
    
        int l = 0, r = nums.size()-1, mid;
        while(l < r){
    
            mid = (l+r)/2;
            if(nums[mid] == nums[mid^1]) 
            	l = mid + 1;
            else r = mid;
        }
        return nums[l];
    }
};

My own （ Judge by length ）：

class Solution {
    
public:
    int singleNonDuplicate(vector<int>& nums) {
    
        //  find  mid  Judge the length of the left and right intervals , Find the odd length and continue to search 
        //  such as  [1,1,2,3,3,4,4] mid  For the first time 3, Then judge whether the length of it and the right interval of the same value is odd , Yes, find , If not, find another 
        int l = 0, r = nums.size()-1, mid, n = nums.size();
        while(l <= r){
    
            mid = (l+r)/2;
            if(mid != 0 && nums[mid] == nums[mid-1]){
    
                if((r-mid)%2 == 0) r = mid-2;
                else l = mid+1;
            }else if(mid != n-1 && nums[mid] == nums[mid+1]){
    
                if((r-mid+1)%2 == 0) r = mid-1;
                else l = mid+2;
            }else break;
        }
        return nums[mid];
    }
};

Complexity analysis

Time complexity ：$O(logn)$, among $n$ It's an array $\text{nums}$ The length of . You need to binary search in the range of the whole array , The time complexity of binary search is $O(\log n)$.
Spatial complexity ：$O(1)$.

Method 2 ： Binary search of even subscripts

Ideas

​​   Because the subscript of the element that appears only once $x$ There are even elements on the left of , So subscript $x$ It must be an even number , You can find it in binary within the even subscript range . The goal of binary search is Find satisfaction $\text{nums}[x]\ne \text{nums}[x+1]$ The smallest even subscript of $x$, Then subscript $x$ The element at is an element that appears only once .

​​   At the beginning , The left bound of binary search is $0$, The right boundary is the maximum even subscript of the array , Because the length of the array is odd , Therefore, the maximum even subscript of the array is equal to the length of the array minus $1$.
​​   Take the average value of the left and right boundaries each time $\text{mid}$ As a subscript to be judged , If $\text{mid}$ If it is an odd number, it will $\text{mid}$ reduce $1$, Make sure $\text{mid}$ It's even .
​​   Compare $\text{nums}[\text{mid}]$ and $\text{nums}[\text{mid}+1]$ Whether it is equal or not , If they are equal $\text{mid}<x$, Adjust the left border , otherwise $\text{mid}\ge x$, Adjust the right border . After adjusting the boundary, continue the binary search , Until the subscript is determined $x$ Value .
​​   Get the subscript $x$ After the value of ,$\text{nums}[x]$ That is, the element that appears only once .

details

consider $\text{mid}$ and $1$ The result of bitwise sum operation , among $\&$ It's the bitwise and operator ：

• When $\text{mid}$ When it's even ,$\text{mid}\&1=0$;
• When $\text{mid}$ It's an odd number ,$\text{mid}\&1=1$.

So in getting $\text{mid}$ After the value of , take $\text{mid}$ The value of minus $\text{mid}\&1$, To ensure the new $\text{mid}$ It's even . If the original $\text{mid}$ If it is an even number, the value remains the same , If the original $\text{mid}$ If it is an odd number, the value is minus $1$.

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    int singleNonDuplicate(vector<int>& nums) {
    
        int low = 0, high = nums.size() - 1;
        while (low < high) {
    
            int mid = (high - low) / 2 + low;
            mid -= mid & 1;
            if (nums[mid] == nums[mid + 1]) {
    
                low = mid + 2;
            } else {
    
                high = mid;
            }
        }
        return nums[low];
    }
};

Complexity analysis

Time complexity ：$O(\log n)$, among $n$ It's an array $\text{nums}$ The length of . You need to find two points in the even subscript range , The time complexity of binary search is $O(\log n)$.
Spatial complexity ：$O(1)$.