Leetcode 540. Single Element in a Sorted Array
Leetcode 540. Single Element in a Sorted Array
Tyan
发布于 2021-09-06 15:40:17
发布于 2021-09-06 15:40:17
文章作者：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]Reference
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-08-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录