Leetcode 540. Single Element in a Sorted Array-蒲公英云

Leetcode 540. Single Element in a Sorted Array

蔚落 2022-09-09 00:13 204阅读 0赞

文章作者：Tyan
博客：noahsnail.com | CSDN | 简书

1. Description

Single Element in a Sorted Array

2. Solution

**解析：**Version 1，使用类似于二分查找的方式寻找单个元素，首先计算中间位置的索引mid，如果mid为奇数，说明数组左半部分有偶数个元素(索引从0开始)，比较nums[mid]与其左边的元素nums[mid-1]，如果二者相等，则表明左半部分一定不存在单个元素，因此left=mid+1，如果二者不相等，则其一定等于右边的元素，此时right=mid-1；如果mid为偶数，明数组左半部分有寄数个元素，比较nums[mid]与其左边的元素nums[mid-1]，如果二者相等，则表明左半部分一定存在单个元素，此时right=mid-2，即移除两个相等元素，如果不相等，则比较nums[mid]与右边的元素nums[mid+1]，如果二者相等，则表明右半部分一定存在单个元素，此时left = mid + 2，如果两者都不满足，说明nums[mid]就是要找的单个元素。注意left < right的边界条件，这样不会出现数组越界的情况，要充分利用索引的奇偶性以及数组存在单个元素时的奇偶性，始终保持下一部分要查找的子数组含有奇数个元素。

Version 1

class Solution:

def singleNonDuplicate(self, nums: List[int]) -> int:
    n = len(nums)
    left = 0
    right = n - 1
    while left < right:
        mid = (left + right) // 2
        if mid % 2 == 1:
            if nums[mid] == nums[mid - 1]:
                left = mid + 1
            else:
                right = mid - 1
        else:
            if nums[mid] == nums[mid - 1]:
                right = mid - 2
            elif nums[mid] == nums[mid + 1]:
                left = mid + 2
            else:
                return nums[mid]
    return nums[left]