题目描述

给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗?

以任意顺序返回这两个数字均可。

示例 1:

1
2
输入: [1]
输出: [2,3]

示例 2:

1
2
输入: [2,3]
输出: [1,4]

提示:

  • nums.length <= 30000

来源:力扣(LeetCode)

题解

数学

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
public int[] missingTwo(int[] nums) {
// 1 + 2 + 3 +...+ n = n(n + 1) / 2
// 1 ^ 1 + 2 ^ 2 + ... + n ^ n = n(n + 1)(2n + 1) / 6
int n = nums.length + 2;
int sum = n * (n + 1) >> 1;
// 注意溢出, 所以循环的时候直接做差值
// long squareSum = n * (n + 1) * (2 * n + 1) / 6;
long squareSum = 0;
for (int i = 0; i <= n; i++) {
if (i < nums.length) {
sum -= nums[i];
squareSum -= nums[i] * nums[i];
}
squareSum += i * i;
}
// x1 + x2 = sum
// x1 ^ 2 + x2 ^ 2 = squareSum
// 2x1x2 = (x1 + x2) ^ 2 - (x1 ^ 2 + x2 ^ 2) = sum * sum - squareSum
// (x1 - x2) ^ 2 = x1 ^ 2 + x2 ^ 2 - 2x1x2 = squareSum - (sum * sum -squareSum) = 2 * squareSum - sum * sum
// x1 - x2 = Math.sqrt(squareSum * 2 - sum * sum)
// x1 = (x1 + x2 + (x1 - x2)) / 2
// x2 = (x1 + x2 - (x1 - x2)) / 2
long diff = (long) Math.sqrt(squareSum * 2 - sum * sum);
return new int[]{(int) (sum - diff) / 2, (int) (sum + diff) / 2};
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

submissions-2022092601

数学求和

1
2
3
4
5
6
7
8
9
10
11
12
public int[] missingTwo(int[] nums) {
int n = nums.length + 2;
int total = (1 + n) * n >> 1;
for (int num : nums) total -= num;
// 求平均值, 两个数字必定一个大于平均值一个小于平均值
int avg = total >> 1;
int subTotal = (1 + avg) * avg >> 1;
for (int num : nums) {
if (num <= avg) subTotal -= num;
}
return new int[]{subTotal, total - subTotal};
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

submissions-2022092602

位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] missingTwo(int[] nums) {
int n = nums.length + 2;
int xorSum = 0;
for (int num : nums) xorSum ^= num;
// 注意从 1 开始
for (int i = 1; i <= n; i++) xorSum ^= i;
int one = 0;
// 最低位的 1, 相当于 Integer.lowestOneBit()
int lowest = (xorSum == Integer.MIN_VALUE) ? xorSum : xorSum & -xorSum;
// 按 xorSum 最低位的 1 所在位置为 0 或 1 分组
for (int num : nums) if ((num & lowest) == 0) one ^= num;
for (int i = 1; i <= n; i++) if ((i & lowest) == 0) one ^= i;
return new int[]{one, xorSum ^ one};
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

submissions-2022092603

标记

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] missingTwo(int[] nums) {
// 标记 n + 1, n + 2 是否出现
int[] temp = new int[]{1, 1};
int n = nums.length;
// nums[i] 出现则将 Math.abs(nums[i]) - 1 下标对应的值 * -1, 也就是变成负数
// 反之, 如果 nums[i] 为负数, 则证明数字 i + 1 出现过
for (int i = 0; i < n; i++) {
int index = Math.abs(nums[i]) - 1;
if (index < n) nums[index] *= -1;
else temp[index - n] = -1;
}
int[] ans = new int[2];
int index = 0;
for (int i = 0; i < n; i++) if (nums[i] > 0) ans[index++] = i + 1;
for (int i = 0; i < 2; i++) if (temp[i] > 0) ans[index++] = n + i + 1;
return ans;
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

submissions-2022092604

参考资料

__END__