Force deduction daily question 540 A single element in an ordered array

540. A single element in an ordered array

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 <= 105
• 0 <= nums[i] <= 105

Answer key

This problem can directly use bit operation for XOR , But the topic requirements are met O(log n) Time complexity and O(1) Spatial complexity .

So choose dichotomy to solve

We can find that what we are given is an ordered array , From this we can get , If an element appears twice , Then these two times are adjacent

So we take the middle number , Then judge the numbers on both sides of him. If he is different from the numbers on both sides , Then this number is the number that only appears once

At the same time, we can also know two conditions

1. If the subscript of the middle number is even ( Judge by array subscript ), And this number is equal to the number at the left end , The number that only appears once must be on his left , And vice versa

   

2. If it's odd , And this number is equal to the number at the left end , The number that only appears once must be at his right end , And vice versa

Code

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int n = nums.length;
        int l = 0, r = n - 1;
        while(l < r){
    
            int mid = l + r >> 1;
            if(mid % 2 == 0){
    
                if(mid + 1 < n && nums[mid] == nums[mid + 1]){
    
                    l = mid + 1;
                }else{
    
                    r = mid;
                }
            }else{
    
                if(mid - 1 >= 0 && nums[mid] == nums[mid - 1]){
    
                    l = mid + 1;
                }else{
    
                    r = mid;
                }
            }
        }
        return nums[r];   
    }
}