题目来源于 LeetCode 上第 540 号问题:有序数组中的单一元素。题目难度为中等,目前通过率60.2%。
给定一个只包含整数的有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: [3,3,7,7,10,11,11]
输出: 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
我们先读题,找出题中关键词“包含整数的有序数组”、‘’元素出现两次“、”只有一个数出现一次“,这里我们可以知道:只出现一次的那个元素所在的有序数组元素个数必为奇数。
这个是解题的关键。
因为题目要求我们的时间复杂度为O(log n),因此我们可以用二分搜索法。
首先将 lo 和 hi 分别指向数组首尾元素,mid 指向中间元素,这时我们会发现中间元素与其左右两边元素分别有以下三种情况,如:
对于第二种情况,我们立马就找到了只出现一次的那个元素。
那么对于第一种情况 mid = mid - 1,那么以(3、3)为界将数组一分为二,判断两边的元素个数,因为我们知道只出现一次的那个元素所在的有序数组元素个数必为奇数,如果(3、3)左边的元素个数为奇数,那么只出现一次的那个数载左边,则将 hi 移到 mid - 2 位置,即(3、3)的左边,如果(3、3)右边的元素个数为奇数,那么只出现一次的那个数在右边,则将 lo 移到 mid + 1 位置,即(3、3)的右边。
第三种情况与第二种情况类似分析,如果(3、3)左边为奇数,则 hi 移到 mid - 1 位置,如果(3、3)右边为奇数,则 lo 移到 mid + 2 位置。以此类推,直到 lo = hi ,搜索结束。
class Solution {
public int singleNonDuplicate(int[] nums) {
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
boolean halvesAreEven = (hi - mid) % 2 == 0;
if (nums[mid + 1] == nums[mid]) {
if (halvesAreEven) {
lo = mid + 2;
} else {
hi = mid - 1;
}
} else if (nums[mid - 1] == nums[mid]) {
if (halvesAreEven) {
hi = mid - 2;
} else {
lo = mid + 1;
}
} else {
return nums[mid];
}
}
return nums[lo];
}
}
我们发现当 mid 索引为偶数时,mid 两边的数组元素个数是偶数,如果 mid 索引为奇数时,mid 两边的数组元素个数为奇数。
当 mid 索引为偶数时,如果 mid = mid + 1
,即解法一的第三种情况,因为mid右边个数为偶数,所以mid+2到hi个数为奇数,那么只出现一次的那个元素肯定在mid的右边,将lo移动到mid+2位置。
如果 mid != mid + 1,那么只出现一次的那个元素肯定在 mid 的左边或者就是 mid 。如果 mid 索引为奇数,那么我们为了保证 mid 索引为偶数,将 mid 移到 mid - 1 位置,这样 mid 索引就变成偶数了,重复上述操作,直到 hi = lo ,搜索结束。
class Solution {
public int singleNonDuplicate(int[] nums) {
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid % 2 == 1) mid--;
if (nums[mid] == nums[mid + 1]) {
lo = mid + 2;
} else {
hi = mid;
}
}
return nums[lo];
}
}