前言
每天和你一起刷 LeetCode 每日一题~
LeetCode 启动!
题目:leetcode.cn/problems/single-element-in-a-sorted-array/description/?envType=daily-question&envId=2024-11-10" rel="nofollow">有序数组中的单一元素
代码与解题思路
先读题:
“一个仅由整数组成的有序数组”
“你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。”
看到这里基本上就能看出来题目要求我们用二分来做这道题目了,这题也是一道经典题目,在题目没给有序以及复杂度要求的时候,直接模拟,用哈希,或者用异或都可以很轻松的解答
怎么用二分做这道题呢?
核心思路:
“有一个数只会出现一次”
我们可以看到,示例一:[1,1,2,3,3,4,4,8,8]
在只出现一次的数字出现之前,偶数下标和下一个奇数下标的元素是相同的,而在特殊数字出现之后,偶数下标和下一个奇数下标的元素就不相同的了
很显然,该数组具有单调性,元素相同证明特殊数字在左区间,元素不相同证明特殊数字在右区间
最后一个问题,怎么样做到每次二分的是偶数下标?让二分上界 / 2,在取到 mid 之后让 mid * 2 这样得到就一定是偶数的下标了~
代码如下:
func singleNonDuplicate(nums []int) int {l, r := 0, len(nums)/2for l < r {mid := (l+r)/2if nums[mid*2] != nums[mid*2+1] {r = mid} else {l = mid + 1}}return nums[l*2]
}
每天进步一点点,我们明天不见不散~
可以和我刷一辈子的每日一题吗?
一题一题,积累起来就是一辈子。