1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int[] findErrorNums(int[] nums) {
int repeat = -1;
for (int i = 0; i < nums.length; i++) {
int targetPos = Math.abs(nums[i]) - 1;
if (nums[targetPos] < 0) {
repeat = Math.abs(nums[i]);
} else {
nums[targetPos] *= -1;
}
}
int missing = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
missing = i + 1;
}
}
return new int[] { repeat, missing };
}
}
|
在原数组上标记.
时间复杂度: O(n)
空间复杂度: O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| public class Solution {
public int[] findErrorNums(int[] nums) {
int xor = 0, xor0 = 0, xor1 = 0;
for (int n : nums)
xor ^= n;
for (int i = 1; i <= nums.length; i++)
xor ^= i;
int rightmostbit = xor & ~(xor - 1);
for (int n : nums) {
if ((n & rightmostbit) != 0)
xor1 ^= n;
else
xor0 ^= n;
}
for (int i = 1; i <= nums.length; i++) {
if ((i & rightmostbit) != 0)
xor1 ^= i;
else
xor0 ^= i;
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] == xor0)
return new int[] { xor0, xor1 };
}
return new int[] { xor1, xor0 };
}
}
|
首先把nums中的元素互相XOR然后把得到的结果再和[1, n]XOR. 最后得到的结果是missing ^ repeat = mrx. 如果把missing和repeat区分出来? 我们知道XOR是相同bit得0, 不同bit得1. mrx的最后边一个bit所在的位置 表示该位置一个num是1, 一个num是0. 于是我们可以用mrx & (mrx - 1)来得到只有在这个位置是1的这个数. 这是因为(mrx - 1)对该位置左侧不影响, 只是flip, 于是它和mrx进行and后的该位置左侧都是0. 对于该位置右侧 由于减去1, 该位置右侧都变为1(如果右侧有bits的话), 该位置变为0. 然后flip后, 该位置变为1, 该位置右侧变为0, 和mrx and后, 由于mrx在该位置本来就是1, 于是最后的结果就是只在该位置是1, 其他位置都是0.
然后我们再去XOR nums中的所有num, 其中在该位置是1的数字和xor1进行xor, 否则和xor2进行xor. 之后再对[1, n] 进行同样的操作. 我们假设重复的数字在该位置是1, 那么此时xor1存的就是repeat; 类似地如果重复的数字在该位置不是1, 此时xor0就是repeat. 最后一个for循环看是否xor0等于nums中的某个num, 如是, 那么xor0存的就是重复的数字, 否则xor1存的就是重复的数字.
很巧妙的方法. 需要记得这个方法.
时间复杂度: O(n)
空间复杂度: O(1)
