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

力扣刷题记录

二分

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

思路

这题的主要思路 直接遍历 依次比较相邻两个是否相同 如果不相同直接返回

但是这样无法达到要求的O(log n)
要达到这个时间复杂度只能二分查找了

mid 偶数
比较 mid mid + 1
相等 low = mid + 1
不等 high = mid

mid 奇数
比较 mid mid - 1
相等 low = mid + 1
不等 high = mid

最后 high == low 此时找到的值

代码

class Solution:def singleNonDuplicate(self, nums: List[int]) -> int:# O(N)# i = 0# while i < len(nums):#     if i < len(nums) - 1 and nums[i] == nums[i+1]:#         i = i + 2#         continue#     else:#         return nums[i]# return 0# mid 偶数  比较 mid     mid + 1# 相等  low = mid + 1# 不等  high = mid l , r = 0, len(nums) - 1while l < r :mid = (l + r) // 2if nums[mid] == nums[mid ^ 1]:l = mid + 1else:r = midreturn nums[l]

时间复杂度：O(log n)
空间复杂度：O(1)