540. 有序数组中的单一元素

Difficulty
Medium
Tags
二分查找
URL
https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
Star
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输出: 10
提示:
  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105
进阶: 采用的方案可以在 O(log n) 时间复杂度和 O(1) 空间复杂度中运行吗？
通过次数41,136提交次数70,721

二分法

思路
将数组按两个元素为一组组合起来。然后将该数组对半分开，且要是的mid始终对着的是某一组的第一个元素。
然后单词出现的元素 其左右两半就会体现出不一样的特征，如下：
notion imagenotion image
在搜索的过程中，切记令mid始终指向对应组的第一个元素，每组第一个元素的下标均为偶数，所以判断当mid % 2 ！= 0 时，可以直接 mid -= 1 ，这时mid指向对应组的第一个元素。
然后具体判断过程如下：
  • 当 nums[mid] == nums[mid + 1] : 说明要找的组别不会出现在当前组及左边，所以left += 2， left直接跳到下一组
  • 当nums[mid] != nums[mid + 1] : 说明要找的组别出现在当前组或者其右边，所以right = mid
题解
class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if mid % 2 == 1:
                mid -= 1
            if nums[mid] == nums[mid+1]:
                left = mid + 2

            elif nums[mid] != nums[mid+1]:
                # 搜索区间是左闭右开的
                # 把字符串按照 2 个一组分开， 单一字符一定是出现在 每一组中的第一个的字符。 切记这是以组为单位进行搜索
                right = mid

        return nums[right]
后来想到的一种简单二分法：
	class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        # 两两元素组成一组，直接搜索哪一组不满足即可
        l, r = 0, len(nums) // 2
        while l < r:
            m = l + (r - l) // 2
            if nums[2 * m] == nums[2*m+1]:
                l = m + 1
            else:
                r = m

        return nums[2*r]