268. 丢失的数字
题目描述
输入一个数组 nums，长度为 n。它装着 n 个互不相同的整数，每个都取自 0 到 n 这 n + 1 个数。
因此 0 到 n 中恰好有一个数没有出现。找出并返回这个数。
输入：nums = [3,0,1] 输出：2
解释：n = 3，范围是 [0,3]，缺的是 2。
输入：nums = [0,1] 输出：2
解释：n = 2，范围是 [0,2]，缺的是 2。
输入：nums = [9,6,4,2,3,5,7,0,1] 输出：8
解释：n = 9，范围是 [0,9]，缺的是 8。
数据范围
n == nums.length1 <= n <= 10^40 <= nums[i] <= nnums里的数两两不同。
进阶：能否用线性时间、常数额外空间解决？
解题思路：排序 + 二分查找
先排序。没缺数之前，每个位置都满足 nums[i] == i；从缺失的数开始，后面每个数都向左挪了一格，变成 nums[i] == i + 1。于是“nums[i] == i”在下标上呈现“前面全真、后面全假”的单调性，用二分找第一个不满足的位置，它就是缺失的数。
为什么正确
区间 [lo, hi) 之外：lo 左边都满足 nums[i] == i，hi 及右边都不满足；答案始终在 [lo, hi] 中。
复杂度分析
时间 O(n log n)（排序为主，二分只需 O(log n)），额外空间 O(1)（不计排序栈）。
易错点
hi 要从 n（数组长度）开始而不是 n-1：缺失的数可能是 n 本身，此时所有位置都满足 nums[i] == i，答案落在数组之外。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def missingNumber(self, nums: List[int]) -> int:
nums.sort()
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] == mid:
lo = mid + 1
else:
hi = mid
return loclass Solution {
public int missingNumber(int[] nums) {
Arrays.sort(nums);
int lo = 0, hi = nums.length;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] == mid) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
}class Solution {
public:
int missingNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int lo = 0, hi = nums.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] == mid) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
};func missingNumber(nums []int) int {
sort.Ints(nums)
lo, hi := 0, len(nums)
for lo < hi {
mid := (lo + hi) / 2
if nums[mid] == mid {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}var missingNumber = function(nums) {
nums.sort((a, b) => a - b);
let lo = 0, hi = nums.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] === mid) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
};function missingNumber(nums: number[]): number {
nums.sort((a, b) => a - b);
let lo = 0, hi = nums.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] === mid) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}其他解法
排序 + 二分把问题转成“第一个 nums[i] != i 的位置”，核心是二分但受排序拖累；异或和求和都利用 0..n 中恰好缺一个数，一遍扫描得出答案。如果数组本身有序，二分只要 O(log n)。
解法 2：位运算（异或） 时间 O(n)，空间 O(1)
把 0 到 n 的所有整数和数组中的所有元素全部异或起来。出现两次的数异或后抵消为 0，最后剩下的就是只在 0..n 中出现、不在数组中的那个数。
线性时间、常数空间，不修改数组，也不会溢出。需要理解异或的抵消性质。
class Solution:
def missingNumber(self, nums: List[int]) -> int:
x = len(nums)
for i, v in enumerate(nums):
x ^= i ^ v
return xclass Solution {
public int missingNumber(int[] nums) {
int x = nums.length;
for (int i = 0; i < nums.length; i++) x ^= i ^ nums[i];
return x;
}
}class Solution {
public:
int missingNumber(vector<int>& nums) {
int x = nums.size();
for (int i = 0; i < (int)nums.size(); i++) x ^= i ^ nums[i];
return x;
}
};func missingNumber(nums []int) int {
x := len(nums)
for i, v := range nums {
x ^= i ^ v
}
return x
}var missingNumber = function(nums) {
let x = nums.length;
for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i];
return x;
};function missingNumber(nums: number[]): number {
let x = nums.length;
for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i];
return x;
}解法 3：数学（求和作差） 时间 O(n)，空间 O(1)
0 到 n 的和是 n(n+1)/2。用它减去数组元素之和，差就是缺失的数。
最容易想到的 O(n) 方法，代码极短。数据范围很大时求和可能溢出，这是异或法没有的问题。
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
return n * (n + 1) // 2 - sum(nums)class Solution {
public int missingNumber(int[] nums) {
long n = nums.length;
long total = n * (n + 1) / 2;
for (int v : nums) total -= v;
return (int) total;
}
}class Solution {
public:
int missingNumber(vector<int>& nums) {
long long n = nums.size();
long long total = n * (n + 1) / 2;
for (int v : nums) total -= v;
return (int)total;
}
};func missingNumber(nums []int) int {
n := len(nums)
total := n * (n + 1) / 2
for _, v := range nums {
total -= v
}
return total
}var missingNumber = function(nums) {
const n = nums.length;
return n * (n + 1) / 2 - nums.reduce((a, b) => a + b, 0);
};function missingNumber(nums: number[]): number {
const n = nums.length;
return n * (n + 1) / 2 - nums.reduce((a, b) => a + b, 0);
}