剑指offer专项突破版(70)—— 排序数组中只出现一次的数字_亚洲第一中锋_哈达迪的博客-爱代码爱编程
题目
剑指 Offer II 070. 排序数组中只出现一次的数字
给定一个只包含整数的有序数组 nums ,每个元素都会出现两次,唯有一个数只会出现一次,请找出这个唯一的数字。
你设计的解决方案必须满足 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
思路
如果输入的数组没有经过排序,则可以用异或的方式来做:
由于两个相同的数字异或的结果是0,因此如果将数组中所有数字异或,最终的结果就
是那个唯一只出现一次的数字,时间复杂度为O(n)
但本题的数据经过排序,可以有更好的解法,即二分法:
- 将数组中的数字两两分为一组
- 最初的若干组数字相等
- 直到遇到只出现一次的数后,后面每一组的数字都不相等
- 因此可以通过二分找到第一个两个数不等的组,该组第一个数就是答案
代码
public int singleNonDuplicate(int[] nums) {
int left = 0;
int right = nums.length / 2;
while (left < right) {
int mid = left + right >> 1;
// 如果已经是最后一组,该组的数就是答案
if (mid == right) {
return nums[nums.length-1];
}
// 判断组内两个数是否相等
if (nums[mid * 2] == nums[mid * 2 + 1]) {
// 找mid后面的组
left = mid + 1;
} else {
// right右边的组不可能成为答案,right和right左边的组有可能
right = mid;
}
}
return nums[left * 2];
}