Leetcode540: a single element in an ordered array

Catalog

1. Title Description

2. Problem solving analysis

2.1 Ideas 1

2.2 Ideas 2

left and right Update

Treatment of boundary conditions

3. Code implementation

---

1. 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 <= 10^5
0 <= nums[i] <= 10^5
 
source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/single-element-in-a-sorted-array
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2. Problem solving analysis

2.1 Ideas 1

         If a number performs bitwise XOR with itself, it will get 0. therefore , As long as all the numbers in the array are bitwise XOR, the final result is the required single element .

         Intuitive approach （ Assume that the array is a） Namely ,a(0) and a(1) Do exclusive or operations , The result is similar to a[2] Do exclusive or operations ,..., Until finally with a[N-1] Do exclusive or operations , That is, get the desired result . But this realization , Although the space complexity meets O(1) The requirements of , Time complexity needs O(N) The computational complexity of , Does not meet the requirements of the topic O(log(N)) Complexity requirements .

2.2 Ideas 2

        As the required time complexity is O(log(N)), So it's natural to imagine dichotomy （ What else can there be besides dichotomy O(log(N)) The time complexity ？）. It has been made clear in the design that the input array is an ordered array , Therefore, the number appearing twice must appear adjacent , The lonely number is different from its front number and its back number . The other numbers in the array are either the same as the number before it or the number after it . Based on this, we can find the lonely number based on dichotomy .

left and right Update

        The key point of dichotomy search is left and right Update . Take... From the conventional dichotomy mid=(left+right)//2("//" means integer division in python) that will do . And this topic is about mid The treatment of is also a little special .

        Because there must be an even number in front of the lonely number , Then there must be even numbers , So the subscript of lonely number （ Consider from 0 At the beginning zero-indexing） It must be even . So if mid=(left+right)//2 For an odd number , Can take mid=mid-1 Adjust to an even number to handle .

         For a mid, If nums[mid] If it is not equal to the number before it and the number after it , Then it is the number you are looking for . If not , Is the search interval the left half or the right half ？

        If ,nums[mid] be equal to nums[mid-1] Words , Because the right half is even , The only lonely number cannot appear in the even number , So the next step is to search the left half . here , It should be maintained left unchanged , And will be right Updated to mid（ Be careful , No mid-1, Because we must keep the length of the search interval odd . This is also slightly different from the general dichotomy ）.

         conversely , If nums[mid] be equal to nums[mid+1] Words , The next step is to search the right half . At this time, we should keep right unchanged , And will be left Updated to mid.

Treatment of boundary conditions

        The above treatment should be compared nums[mid],nums[mid-1]  as well as nums[mid+1]. When mid=0 perhaps mid=N-1 when , Appropriate boundary processing is needed to avoid cross-border errors .

        Of course , And don't forget , There is only one number input .

        Besides , The case that the length of the input array is even is an exception , You need to consider the input legitimacy check .

3. Code implementation

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        N     = len(nums)        
        if N==1:
            return nums[0]
        if N%2 == 0:
            return None
        left  = 0
        right = N - 1
        
        # Boundary check
        if nums[0] != nums[1]:
            return nums[0]
        if nums[-1] != nums[-2]:
            return nums[-1]        
        cnt = 0                
        while left <= right:
            if left == right:
                return nums[left]

            mid   = (left+right) // 2
            # print(left,right,mid)
            if mid%2 == 1:
                mid = mid - 1            

            if (nums[mid] != nums[mid-1]) and (nums[mid] != nums[mid+1]):
                return nums[mid]
            
            if nums[mid] == nums[mid-1]:
                right = mid
            else:
                left  = mid   

if __name__ == '__main__':        
    
    sln = Solution()

    nums = [1,1,2,3,3,4,4,8,8]
    print(sln.singleNonDuplicate(nums))            
    
    nums = [3,3,7,7,10,11,11]
    print(sln.singleNonDuplicate(nums))            
    
    nums = [3,3,7,7,9,9,10]
    print(sln.singleNonDuplicate(nums))            
    
    nums = [2,3,3,4,4,8,8]
    print(sln.singleNonDuplicate(nums))            
        
    nums = [2]
    print(sln.singleNonDuplicate(nums))            
    
    nums = [2,2,3,3]
    print(sln.singleNonDuplicate(nums))