540. 有序数组中的单一元素
题目描述
给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n)
时间复杂度和 O(1)
空间复杂度。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8] 输出: 2
示例 2:
输入: nums = [3,3,7,7,10,11,11] 输出: 10
提示:
1 <= nums.length <= 105
0 <= nums[i] <= 105
解法
方法一:二分查找
给与的数组是有序的,由此可以使用二分查找,那条件该如何判断呢。
先观察一下线性遍历是如何确定目标的:
for (int i = 0; i < n - 1; i += 2) {
if (nums[i] != nums[i + 1]) {
return nums[i];
}
}
return nums[n - 1];
偶数下标:当 nums[i] != nums[i + 1] && i % 2 == 0
成立,结果便是 nums[i]
。
奇数下标:当 nums[i] != nums[i - 1] && i % 2 == 1
成立,结果便是 nums[i - 1]
。
于是二分模板就有了:
l = 0
r = n - 1
while l < r
m = l + (r - l) / 2
if m % 2 == 0
if nums[m] == nums[m + 1]
l = m + 1
else
r = m
else
if nums[m] == nums[m - 1]
l = m + 1
else
r = m
return nums[l]
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|