2021/04/18
2022-02-14 每日一题，异或改造
注意到 check 函数也可以写成这样子
在奇点的右边，如果是奇数下标，那么一定满足 nums[mid] == nums[mid+1]
private boolean check(int[] nums, int mid) {
if (mid % 2 == 0) {
return nums[mid] != nums[mid+1];
} else {
return nums[mid] == nums[mid+1];
}
}
那么可以用异或运算来去掉这个 if
class Solution {
public int singleNonDuplicate(int[] nums) {
int l = 0;
int r = nums.length - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (((mid % 2) ^ (nums[mid] != nums[mid+1] ? 1 : 0)) == 1) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l];
}
}
2021-04-18 二分模板法
数组长度一定是奇数，奇点只可能是偶数下标。
1 1 2 2 3 3 4 4 5 5 6 7 7 8 8 9 9
0 2 4 6 8 10 12 14 16
可以看到，在奇点的左边，偶数下标都是靠左边的数，在奇点的右边，偶数下标都是靠右边的数。
或者说对于所有偶数下标 $i$,在奇点的左边，都满足
\[\text{N}_i == \text{N}_{i+1}\]在奇点的右边（包括奇点本身）都满足
\[\text{N}_i \neq \text{N}_{i+1}\]我们只需要判断，从什么时候开始，偶数下标第一次满足了 $N_i \neq N_{i+1}$ ，那么这个偶数下标就是我们得到的奇点。
二分时去掉最后一个元素，如果没搜到，此时 l 一定指向的是最后这个偶数下标的元素。
impl Solution {
pub fn check(mid: usize, nums: &Vec<i32>) -> bool {
return if mid % 2 == 0 {
nums[mid] != nums[mid + 1]
} else {
nums[mid - 1] != nums[mid]
}
}
pub fn single_non_duplicate(nums: Vec<i32>) -> i32 {
let mut l = 0;
let mut r = nums.len() - 1;
while l < r {
let mut mid = l + (r - l) / 2;
if Solution::check(mid, &nums) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l];
}
}
2021-01-22 配对消除
题目描述
升序数组，每个数组元素出现了两次，只有一个出现了一次，把这个数字揪出来。要求时间复杂度是log(n)
分析
这个复杂度，肯定需要二分，当我们求出 mid 的值之后，接下来怎样进一步的确定在左边还是在右边，是需要思考的。
方法是，二分之后，mid 如果有重复的，那么 mid 跟与它相同的数一起消掉后，数组被分成了两个部分，target 应该出现在长度为奇数的那半边。
实现
递归写法：
class Solution {
public int singleNonDuplicate(int[] nums) {
return singleNonDuplicate(nums, 0, nums.length - 1);
}
public int singleNonDuplicate(int[] nums, int i, int j) {
if (i == j) {
return nums[i];
}
int mid = (i + j) / 2;
int l = nums[mid - 1], m = nums[mid], r = nums[mid + 1];
if (l != m && m != r) return m;
if (l == m) { // 跟左边的消了
if ((mid - 2 - i + 1) % 2 == 0) { // 左边是偶数个，所以在右边
return singleNonDuplicate(nums, mid + 1, j);
} else {
return singleNonDuplicate(nums, i, mid - 2);
}
} else {
if ((j - (mid + 2) + 1) % 2 == 0) { // 右边是偶数个，所以在左边
return singleNonDuplicate(nums, i, mid - 1);
} else {
return singleNonDuplicate(nums, mid + 2, j);
}
}
}
}
由于递归的空间复杂度比较高，用 while 循环改写一下，也比较简单：
class Solution {
public int singleNonDuplicate(int[] nums) {
int i = 0, j = nums.length - 1;
while (true) {
if (i == j) return nums[i];
int mid = (i + j) / 2;
int l = nums[mid - 1], m = nums[mid], r = nums[mid + 1];
if (l != m && m != r) return m;
if (l == m) { // 跟左边的消了
if ((mid - 2 - i + 1) % 2 == 0) { // 左边是偶数个，所以在右边
i = mid + 1;
} else {
j = mid - 2;
}
} else {
if ((j - (mid + 2) + 1) % 2 == 0) { // 右边是偶数个，所以在左边
j = mid - 1;
} else {
i = mid + 2;
}
}
}
}
}