Two points -leetcode-540 A single element in an ordered array

540. A single element in an ordered array

Title Description

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 .

Tips :

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

violence

Pure violence is the use of a map, Record the number of times each element appears . then , Take the element that only appears once as the result . like that The space complexity is $O(n)$, The following method is only a small optimization in space , In terms of time, it is still a violent solution …

Ideas

• Because the title has required the array to be ordered , And “ Each element appears twice , Only one number will appear once ”
• therefore , You can go from front to back , Scan every two , Until you find a group of neighbors 2 Elements Unequal until .

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int n = nums.length;
        if (n == 1) return nums[0];
        int i = 1;
        for ( ; i < n; i += 2) {
    
            if (nums[i] != nums[i - 1]) break;
        }
        System.out.println("i = " + i);
        return nums[i - 1];
    }
}

• Time complexity ：$O(n)$
• Spatial complexity ：$O(1)$

The title requires time in $O(longn)$, This solution is not ok

An operation

Ideas ：

• It's a question “ Each element appears twice , Only one number will appear once ”
• This is exactly in line with “ Exclusive or ” Thought , So you can go through “ Exclusive or ” solve …

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
    
            //  Exclusive or   operation 
            res ^= nums[i];
        }
        return res;
    }
}

• Time complexity ：$O(n)$
• Spatial complexity ：$O(1)$
  

Two points

ps： Today is Valentine's Day , Two points for the dog （wo） It's too mixed

Reference resources ： Brother Tong - Answer key

class Solution {
    
    public int singleNonDuplicate(int[] nums) {
    
        //  Two points search 
        int left = 0, right = nums.length - 1;
        while (left < right) {
    
            int mid = (left + right) / 2;
            if (mid % 2 == 0) {
    
                if (nums[mid] == nums[mid + 1]) {
    
                    left = mid + 1;
                } else {
    
                    right = mid;
                }
            } else {
    
                if (nums[mid] == nums[mid - 1]) {
    
                    left = mid + 1;
                } else {
    
                    right = mid;
                }
            }
        }
        return nums[right];
    }
}