当前位置：网站首页>540. Single element in 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 .

Here is an example ：

Tips ：

1 <= nums.length <= 105
0 <= nums[i] <= 105

Two 、 Ideas

1、 Their thinking

1. Train of thought

The requirements given in the title here are ：

Time complexity
Spatial complexity

Obviously, you need to use Two points search To solve the problem .

The title says Ordered array And Each element appears twice , Only one number will appear once . Then look at the example and we can find ： Set the current subscript to x

In the presence of Unique number Before , When x For even when , It must be Satisfy nums[ x ] = nums[ x + 1 ], if x Is odd , You must be satisfied nums[ x ] = nums[ x - 1 ].
There is Unique number after , When x For even when , It must be Satisfy nums[ x ] = nums[ x - 1 ], if x Is odd , You must be satisfied nums[ x ] = nums[ x + 1 ].

Therefore, we can proceed according to the above conditions Dichotomous condition The judgment of the , because Will only appear One Unique number , So the array nums It must be the size of Odd number .

Let's assume that the current subscript is x ：

If x Is odd , Then with x The number on the left is equal , It's not equal Then the unique number is mid Left side , equal shows Unique number stay x To the right of .
If x It's even , Then with x The number on the right is equal , It's not equal Then the unique number is mid Left side , equal Then the unique number is x To the right of .

According to the above conditions , You can write a binary search , What we use here is Exclusive or ( ^ ) To distinguish the current mid Of Parity , It's really clever .

2. Train of thought two

Here's what I think , Search for two elements every time you jump , Until you find nums[ x ] ！= nums[ x + 1 ] When , that nums[ x ], It must be that The only element .

2、 Extreme case judgment

For method two ： What needs to be noted here is , Judge the condition Cannot let subscript x + 1 Transboundary , Then you can't judge the last element , And can't judge nums size by 1 The situation of .

3、 Extreme situation resolution

It can be found that if the judgment comes to the end , If you don't find the only element , Then the only element can only be the last ; If there is only one element , Then the only element is also the last element . So here's the solution , Finally, directly return nums[ nums.size() - 1 ] , that will do .

3、 ... and 、 Problem solving

1、 Code implementation

1. Method 1

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            // Every time I find  left  And  right  The number in the middle   Judge 
            int mid = (right - left) / 2 + left;
            // Here we use and  1  Exclusive or   It's perfect  
            // because   If  mid  Is odd   Then compare with the number on the left , If  mid  It's even   Then compare with the number on the right 
            // The dichotomy here is ： Two numbers are equal   Then it must be  mid  A unique number appears on the right  
            if (nums[mid] == nums[mid ^ 1]) {
                left = mid + 1;
            }
            // If it's not equal   shows   The order must have been disrupted on the left . 
            else {
                right = mid;
            }
        }
        return nums[left];
    }
};

2. Method 2

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int numsLength = nums.size();
        for(int i = 0; i < numsLength - 1; i += 2){
            if(nums[i] == nums[i+1]){
                continue;
            }else{
                return nums[i];
            }
        }
        return nums[numsLength - 1];
    }
};