Leetcode 540. Single Element in a Sorted Array

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

文章作者：Tyan  
博客：[noahsnail.com][] | [CSDN][] | [简书][Link 1]

## 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]

## Reference ##

1.  [https://leetcode.com/problems/single-element-in-a-sorted-array/][https_leetcode.com_problems_single-element-in-a-sorted-array]

[noahsnail.com]: http://noahsnail.com
[CSDN]: http://blog.csdn.net/quincuntial
[Link 1]: http://www.jianshu.com/users/7731e83f3a4e/latest_articles
[Single Element in a Sorted Array]: /images/20220829/fec19db29bf34f979d3a53c69237046f.png
[https_leetcode.com_problems_single-element-in-a-sorted-array]: https://leetcode.com/problems/single-element-in-a-sorted-array/