LeetCode #540 有序数组中的单一元素 二分查找
程序员文章站
2024-03-17 16:43:40
...
LeetCode #540 有序数组中的单一元素
题目描述
给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: [3,3,7,7,10,11,11]
输出: 10
注意: 您的方案应该在 O(log n)
时间复杂度和 O(1)
空间复杂度中运行。
思路分析
题目规定了 O(logN)
的时间复杂度,因此不能遍历数组,那就只能二分查找了
这道题巧妙的地方在于除了待找的数,其他数都出现两次,这说明待找的数将数组分成了两个区域:
- 在这个数左边:
nums[m] == nums[m+1]
- 在这个数右边:
nums[m] != num[m+1]
所以在二分查找时每次都将 mid 取偶数这样可以快速判断这个数是在左边还是在右边
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
left = 0; right = len(nums) - 1
while left < right:
mid = left + (right - left) // 2
# 使left/mid/right都位偶数
if mid % 2 == 1:
mid -= 1
# 如果nums[mid] == nums[mid+1],要找的数在[mid+2,right]
if nums[mid] == nums[mid+1]:
left = mid + 2
# nums[mid] != nums[mid+1],说明要找的数在[left,mid](可能是nums[mid]))本身,所以循环退出条件为left<right
else:
right = mid
return nums[left]
- 时间复杂度:
- 空间复杂度:
上一篇: 箭头函数参数和返回值
下一篇: 顺序查找—Java实现
推荐阅读
-
LeetCode #540 有序数组中的单一元素 二分查找
-
540. 有序数组中的单一元素——二分查找
-
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array(C语言)
-
二分法查找,返回有序数组中第一个大于给定值的元素的索引
-
在一个有序数组中,查找具体的某个数(二分查找)
-
写代码可以在整型有序数组中查找想要的数字(二分查找)
-
【笔记】二分法,有序数组中快速寻找某个元素的下标
-
在一个有序(增序)数组中查找具体的某个数字n 与二分法查找算法
-
二分法查找有序数组中某元素个数
-
[二分法]leetcode1157:子数组中占绝大多数的元素(hard)