题目
给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 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 <= 1e5
- 0 <= nums[i] <= 1e5
思路
- 只能二分了
- 只有一个不同的数字,那么该数字前后都有偶数个数
- 对于数组下标从0开始,那么该数的下标只能为偶数
有两种二z的方法
- 1、二分偶数下标
- 和下面一样
- 2、二分全局数组,
- 1、对于偶数下标mid的数,只需比较下标mid + 1的数字与其是否相同
- 相同说明答案下标>=mid + 2
- 否则r = mid
- 2、对于奇数下标,该数只能与其前面那个数构成一对
题解
1
int singleNonDuplicate(int* nums, int numsSize){
if (numsSize == 1) return nums[0];
int l = 0, r = numsSize - 1;
while (l < r) {
int ind = ((r - l) >> 1) + l;
ind -= ind & 1; //变成偶数
if (nums[ind] == nums[ind + 1]) {
l = ind + 2;
} else r = ind;
}
return nums[l];
}
2
int singleNonDuplicate(int* nums, int numsSize){
if (numsSize == 1) return nums[0];
int l = 0, r = numsSize - 1;
while (l < r) {
int mid = ((r - l) >> 1) + l;
if (nums[mid] == nums[mid ^ 1]) l = mid + 1;
else r = mid;
//利用位运算替换下面注释的代码
// if (mid & 1) {
// if (nums[mid] == nums[mid - 1]) l = mid + 1;
// else r = mid;
// } else {
// if (nums[mid] != nums[mid + 1]) r = mid;
// else l = mid + 1;
// }
}
return nums[l];
}
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/single-element-in-a-sorted-array