540. 有序数组中的单一元素——二分查找
程序员文章站
2024-03-17 16:34:40
...
传送门:https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
题目
给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
思路
一个仅由整数组成的、每个元素都会出现两次的有序数组,满足一下性质:
- 每个元素必成对出现
- 若下标x为偶数,则nums[x] = nums[x + 1]
- 若下标x为奇数,则nums[x - 1] = nums[x]
如果在数组中有一个数只出现了一次
则在这个数左侧的子数组仍然满足上述性质
但这个数右侧的子数组的就不满足上述性质
所以,目标数的左右两侧有明显的性质差别,这就是运用二分查找的依据
每次对二分的mid做判断,如果满足上述性质就继续查找右侧,否则继续查找左侧。
技巧
官方题解有个判断上述性质的巧妙方法:
利用按位异或的性质,可以得到 mid和相邻的数之间的如下关系,其中 ⊕ 是按位异或运算符:
当mid是偶数, mid + 1 = mid ⊕ 1
当mid是奇数,mid - 1 = mid ⊕ 1
因此在二分查找的过程中,不需要判断 mid 的奇偶性,mid 和 mid ⊕1 即为每次需要比较元素的两个下标。
附官方题解代码
class Solution {
public int singleNonDuplicate(int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high) {
int mid = (high - low) >> 1 + low;
if (nums[mid] == nums[mid ^ 1]) {
low = mid + 1;
} else {
high = mid;
}
}
return nums[low];
}
}
参考
上一篇: JS基础day03-函数上
下一篇: 顺序查找和二分查找----java实现
推荐阅读
-
540. 有序数组中的单一元素——二分查找
-
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array(C语言)
-
二分法查找,返回有序数组中第一个大于给定值的元素的索引
-
在一个有序数组中,查找具体的某个数(二分查找)
-
函数在整型有序数组中查找想要的数字(折半查找)
-
JAVA----二分法查找有序数组元素位置
-
写代码可以在整型有序数组中查找想要的数字(二分查找)
-
【笔记】二分法,有序数组中快速寻找某个元素的下标
-
一个函数实现一个整形有序数组的二分查找
-
实现有序数组的二分查找 C语言