Single element of an ordered array

Single element of an ordered array

Topic link ：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 .

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

Solution 1 ：

Because in addition to that single element in the array , Other elements appear in pairs , So we can use XOR , Use a variable to XOR all the numbers in the array once , The final result is the single element .

x^x = 0,x^0 = x;

Time complexity O(N)

Spatial complexity O(1)

class Solution {
    
public:
    int singleNonDuplicate(vector<int>& nums) {
    
        // Record the final answer 
        int ans = 0;
        for(int i = 0;i<nums.size();i++)
        {
    
            ans^=nums[i];
        }
        return ans;
    }
};

Solution 2 ：

We can also use the dichotomy method to solve this problem .

We can think about it like this ： Before this single element existed , The numbers of arrays are all 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 .

When we insert this single element into the array , The first half of the single element will still have the above conclusion , However, the latter half of a single element will cause the conclusion to flip due to the insertion of the single element . Thus there are ： The subscript corresponding to the first of the paired elements must be odd , The subscript corresponding to the second of the paired elements must be even .

Therefore, the duality of our problem comes out , We can according to the equinox mid To discuss the situation according to the parity of ：

• If mid The subscript is even , According to the initial conclusion , Under normal circumstances, the value of the even subscript will be equal to the value of the next number . So if this condition is met , Prove that the single element is not mid Left side , It should be in mid The right side of does not include mid, So we update the interval to [mid+1,right], On the contrary, if the current mid If it is not equal to the value of the next number , Then the value of a single element should be mid The left side of includes mid, Therefore, the update interval is [left,mid]
• If mid Subscripts are odd , According to the initial conclusion , Under normal circumstances, the value of an odd subscript will be equal to the value of its previous number . So if this condition is met , Prove that the single element is not mid Left side , It should be in mid The right side of does not include mid, So we update the interval to [mid+1,right], On the contrary, if the current mid If it is not equal to the value of its previous number , Then the value of a single element should be mid The left side of includes mid, Therefore, the update interval is [left,mid]

Time complexity O(logN)

Spatial complexity O(1)

class Solution {
    
public:
    int singleNonDuplicate(vector<int>& nums) {
    
        int n = nums.size();
        // It's a special verdict 
        if(n==1)
        {
    
            return nums[0];
        }
        // Dichotomous thinking 
        // Before the existence of this single element , The numbers in the array are all in pairs , So the number of pairs   The subscript of the first number is even, and the subscript of the second number is odd 
        // But after inserting this single element into a certain position , The first half of the data of the single element will still keep the subscript of the first number even , The subscript of the second number is odd 
        // But in the second half of the single element, the nature of the data will change 
        // The second half of the data will become ： The subscript of the first number of paired data is odd , The subscript of the second number is even 
        int left = 0;
        int right = n-1;
        while(left<right)
        {
    
            int mid = left+(right-left)/2;
            // If mid The value of the subscript is even 
            if((mid&1)==0)
            {
    
                // If mid Subscript value and mid+1 The values of subscripts are equal 
                // The number that proves to occur only once appears in mid The right side of does not include mid
                // Therefore, the update interval is [mid+1,right]
                if(mid+1<n&&nums[mid]==nums[mid+1])
                {
    
                    left = mid+1;
                }
                // Otherwise, the update interval is [left,mid]
                else
                {
    
                    right = mid;
                }
            }
            // If mid The value of the subscript is an odd number 
            else
            {
    
                // If mid Subscript value and mid-1 The value of is equal 
                // The number that proves to appear only once is mid The right side of does not include mid
                // Therefore, the update interval is [mid+1,right]
                if(mid-1>=0&&nums[mid-1]==nums[mid])
                {
    
                    left = mid+1;
                }
                // Otherwise, the update interval is [left,mid]
                else
                {
    
                    right = mid;
                }
            }
        }

        return nums[right];
    }
};