【leetcode】540. Single Element in a Sorted Array

时间:2022-11-16 10:48:33

题目如下:

【leetcode】540. Single Element in a Sorted Array

解题思路:题目要求时间复杂度是O(logN),可以尝试使用二分查找法。首先数组是有序的,而且仅有一个元素出现一次,其余均为两次。我们可以先找到数组最中间的元素,记为mid。如果mid和mid-1以及mid+1都不相同,那么mid就是single number。如果mid和mid-1相同,就要分两种情况,a.mid是奇数,single number会出现在mid的右半边;b.mid是偶数,出现在左半边。同理,如果mid和mid+1相同,那么是相反的:a.mid是奇数,出现在左半边;b.mid是偶数,出现在右半边。得到这个规律后,就可以放心的使用二分查找了。

代码如下

class Solution(object):
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low = 0
        high = len(nums)-1
        res = 0
        while low <= high:
            mid = (low + high) /2
            #print mid,nums[mid]
            if mid == 0 or mid == len(nums)-1:
                res = nums[mid]
                break
            if nums[mid] == nums[mid +1]:
                if mid % 2 == 1:
                    high = mid - 1
                else:
                    low = mid + 1
            elif nums[mid] == nums[mid-1]:
                if mid % 2 == 1:
                    low = mid + 1
                else:
                    high = mid - 1
            else:
                res = nums[mid]
                break
        return res