Intuitive Python solution


  • 0
    M

    Perform binary search, updating the search to the subarray with odd length.

    class Solution(object):
        def singleNonDuplicate(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            lower = 0
            upper = len(nums) - 1
            while lower < upper:
                mid = (lower + upper) / 2
                n = upper - mid - 1
                if nums[mid] == nums[mid+1]:
                    if n % 2 == 0:
                        upper = mid - 1
                    else:
                        lower = mid + 2
                elif nums[mid] == nums[mid-1]:
                    if n % 2 == 0:
                        lower = mid + 1
                    else:
                        upper = mid - 2
                else:
                    return nums[mid]
            return nums[lower]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.