Python Solution with Binary search with O(log(n))


  • 0
    Z

    in short, it is a binary search
    think this without the single element
    since now it is even number length, middle index would always be the element of the pair.
    Now we have a single element been add between these pair

    so now if we get the middle, if it is not the end of the pair ,then the single element been added at the front of the middle. otherwise it been add to the after the middle.

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

Log in to reply
 

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