LeetCode 268 Missing Number 缺失数字全解：排序、哈希集合、位运算 XOR 与数学求和四种解法对比

LeetCode 268 Missing Number 缺失数字全解排序、哈希集合、位运算 XOR 与数学求和四种解法对比【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读Missing Number缺失数字是 LeetCode 上经典的数组入门题给定一个包含n个互不相同数字的数组数字取自[0, n]区间其中恰好缺失一个数字要求找出它。本仓库以 articles/missing-number.md 为主干完整收录了排序、哈希集合、位运算 XOR 与数学求和四种解法并在 python/、cpp/、go/、rust/、javascript/ 等十余种语言目录下提供了对应实现如 cpp/0268-missing-number.cpp、python/0268-missing-number.py。读完本文你将掌握这道题的四种解题思路、时间复杂度对比以及常见的边界陷阱能够举一反三地迁移到其他查找缺失/重复元素类问题。前置知识在动手解决本题之前建议先熟悉以下三个基础概念它们是文中四种解法的底层支撑位运算 XOR异或XOR 解法利用a ^ a 0的性质让所有成对出现的数字互相抵消最终只剩下缺失的那个数字。数学求和公式数学解法利用0到n连续整数的求和公式用期望总和减去数组实际总和得到缺失值。哈希集合Hash Set哈希解法利用集合的常数时间查找能力快速判断[0, n]中哪个数字没有出现在数组里。仓库中的 hints/missing-number.md 给出了官方的进阶提示脉络从暴力O(n²)的逐个比对到用哈希集合优化为O(n)时间再到用位运算进一步把空间压缩到O(1)完整呈现了从朴素到最优的思维进化路径。问题定义与边界条件数组长度为n其中包含n个互不相同的数字全部取自区间[0, n]。由于区间内有n 1个整数而数组只有n个元素因此恰好缺失一个数字。关键边界条件有两个缺失数字可能是n本身。例如nums [0, 1]n 2缺失的是2也就是n。任何只遍历索引0到n - 1的解法都会漏掉这个答案。数组是无序的。输入并不保证排序因此排序解法必须显式先排序其他解法则完全不受顺序影响。仓库 cpp/0268-missing-number.cpp 的注释中用两个例子说明了这一设定nums [3, 0, 1]缺失2nums [0, 1]缺失2。解法一排序Sorting核心直觉如果数组是完整且有序的那么索引i位置上的值应当恰好等于i。一旦出现nums[i] ! i这个索引i就是缺失的数字。排序把乱序数组排好让这个对比变得直观是最适合初学者理解的做法。算法步骤将数组按升序排序。从索引0遍历到n - 1若nums[i] ! i说明i缺失直接返回i。若所有索引都与值匹配说明缺失的是n返回n。以nums [3, 0, 1]为例排序后为[0, 1, 3]i 0时nums[0] 0i 1时nums[1] 1i 2时nums[2] 3 ! 2返回2。多语言实现class Solution: def missingNumber(self, nums: List[int]) - int: n len(nums) nums.sort() for i in range(n): if nums[i] ! i: return i return nclass Solution { public: int missingNumber(vectorint nums) { int n nums.size(); sort(nums.begin(), nums.end()); for (int i 0; i n; i) { if (nums[i] ! i) { return i; } } return n; } };public class Solution { public int missingNumber(int[] nums) { int n nums.length; Arrays.sort(nums); for (int i 0; i n; i) { if (nums[i] ! i) { return i; } } return n; } }class Solution { /** * param {number[]} nums * return {number} */ missingNumber(nums) { let n nums.length; nums.sort((a, b) a - b); for (let i 0; i n; i) { if (nums[i] ! i) { return i; } } return n; } }func missingNumber(nums []int) int { n : len(nums) sort.Ints(nums) for i : 0; i n; i { if nums[i] ! i { return i } } return n }impl Solution { pub fn missing_number(nums: Veci32) - i32 { let n nums.len() as i32; let mut nums nums; nums.sort(); for i in 0..nums.len() { if nums[i] ! i as i32 { return i as i32; } } n } }仓库中 C、C#、Kotlin、Swift 等语言的排序实现同样遵循这一模式可分别参考 c/0268-missing-number.c、csharp/0268-missing-number.cs、kotlin/0268-missing-number.kt、swift/0268-missing-number.swift。复杂度分析时间复杂度$O(n \log n)$主要开销来自排序。空间复杂度$O(1)$ 或 $O(n)$取决于排序算法是否使用额外空间。解法二哈希集合Hash Set核心直觉核心问题是能否快速判断某个数字是否存在于数组中。把数组元素全部放入哈希集合后对任意数字的成员判断都能在常数时间内完成。随后只需在[0, n]范围内逐个检查第一个不在集合中的数字就是答案。这种做法用少量额外空间换来了非常清晰简单的逻辑。算法步骤将数组所有元素插入哈希集合。遍历0到n的所有数字若某个数字不在集合中返回它作为缺失数字。因为恰好只有一个数字缺失该过程必然找到答案。多语言实现class Solution: def missingNumber(self, nums: List[int]) - int: num_set set(nums) n len(nums) for i in range(n 1): if i not in num_set: return iclass Solution { public: int missingNumber(vectorint nums) { unordered_setint num_set(nums.begin(), nums.end()); int n nums.size(); for (int i 0; i n; i) { if (num_set.find(i) num_set.end()) { return i; } } return -1; } };func missingNumber(nums []int) int { numSet : make(map[int]struct{}) for _, num : range nums { numSet[num] struct{}{} } n : len(nums) for i : 0; i n; i { if _, exists : numSet[i]; !exists { return i } } return -1 }其余语言的实现大同小异Java 使用HashSetJavaScript 使用SetKotlin 使用nums.toSet()Swift 使用Set(nums)Rust 使用HashSeti32收集迭代器此处不再逐一展开。注意循环上界是n含因为n本身可能是缺失值。复杂度分析时间复杂度$O(n)$插入与查询均为常数时间。空间复杂度$O(n)$用于存储哈希集合。解法三位运算 XORBitwise XOR核心直觉XOR 拥有三个关键性质a ^ a 0数字与自己异或抵消a ^ 0 aXOR 满足交换律与结合律运算顺序无关紧要因此把0到n的全部数字与数组中的全部数字一起异或每个在两边都出现的数字都会成对抵消最终剩下的只有缺失的那个数字。该方案无需排序也无需额外数据结构即可在线性时间、常数空间内求解。仓库 cpp/0268-missing-number.cpp 顶部注释用nums [0, 1, 3, 4]推导了完整过程Missing 4^(0^0)^(1^1)^(2^3)^(3^4) (4^4)^(0^0)^(1^1)^(3^3)^2 0^0^0^0^2 2这正是a ^ a 0与交换结合律的直观体现。算法步骤令n为数组长度。初始化变量xorr n先纳入缺失候选值n。遍历i从0到n - 1xorr ^ ixorr ^ nums[i]循环结束后xorr即缺失数字返回它。多语言实现class Solution: def missingNumber(self, nums: List[int]) - int: n len(nums) xorr n for i in range(n): xorr ^ i ^ nums[i] return xorrclass Solution { public: int missingNumber(vectorint nums) { int n nums.size(); int xorr n; for (int i 0; i n; i) { xorr ^ i ^ nums[i]; } return xorr; } };impl Solution { pub fn missing_number(nums: Veci32) - i32 { let n nums.len() as i32; let mut xorr n; for i in 0..nums.len() { xorr ^ i as i32 ^ nums[i]; } xorr } }/** * https://leetcode.com/problems/missing-number/ * Time O(N) | Space O(1) * param {number[]} nums * return {number} */ var missingNumber function (nums, missingNumber nums.length) { for (let i 0; i nums.length; i) { const xor i ^ nums[i]; missingNumber ^ xor; } return missingNumber; };仓库中的 rust/0268-missing-number.rs 与 javascript/0268-missing-number.js 采用了完全相同的 XOR 策略其中 JavaScript 版本利用默认参数把n直接作为missingNumber的初始值写法更为紧凑。复杂度分析时间复杂度$O(n)$单次线性遍历。空间复杂度$O(1)$仅使用一个整型变量。解法四数学求和Math核心直觉数学观察非常简洁0到n的连续整数之和是已知的。用期望总和减去数组实际元素之和差值就是缺失的数字。为避免分别计算两个总和可能带来的溢出问题可以在单次循环中边加边减res初始为n每轮先加i再减nums[i]循环结束后res即为答案。这样既保持了逻辑干净又在部分语言中规避了溢出风险。算法步骤令n为数组长度。初始化变量res n。遍历i从0到n - 1res ires - nums[i]循环结束后res即缺失数字返回它。多语言实现class Solution: def missingNumber(self, nums: List[int]) - int: res len(nums) for i in range(len(nums)): res i - nums[i] return resfunc missingNumber(nums []int) int { res : len(nums) for i : 0; i len(nums); i { res i - nums[i] } return res }public class Solution { public int missingNumber(int[] nums) { int res nums.length; for (int i 0; i nums.length; i) { res i - nums[i]; } return res; } }class Solution { func missingNumber(_ nums: [Int]) - Int { var res nums.count for i in 0...nums.count-1 { res i - nums[i] } return res } }仓库中的 python/0268-missing-number.py 与 go/0268-missing-number.go 正是该单循环边加边减写法的实现。需要注意的是java/0268-missing-number.java 选择了另一种等价写法先计算total n * (n 1) / 2再减去数组和sum得到答案——这对应原文档中提到的先算完整期望和的版本在n极大时存在溢出风险需结合语言整数类型谨慎使用。复杂度分析时间复杂度$O(n)$。空间复杂度$O(1)$。常见陷阱Common Pitfalls陷阱一忘记n本身可能就是缺失值数组长度为n取值范围是[0, n]因此n本身也可能缺失。只检查索引0到n - 1的解法会在其他数字全部齐全时漏掉n无法返回正确答案。四种解法都通过循环结束后返回n或初始值设为n的方式覆盖了这一情况。陷阱二求和方案的整数溢出使用数学方法时若先单独计算完整期望和n * (n 1) / 2再相减当n很大时可能发生整数溢出。把加法和减法合并到同一个循环中res i - nums[i]可有效规避该问题这也是原文档推荐单循环写法的原因。若必须使用两段式写法如 java/0268-missing-number.java应确认语言整数类型能容纳n * (n 1)的上限。四种解法对比总结解法核心思想时间复杂度空间复杂度是否原地适用场景排序排好序后比较nums[i]与i$O(n \log n)$$O(1)$ 或 $O(n)$取决于排序算法初学者理解有序对比哈希集合集合常数时间成员查询$O(n)$$O(n)$否逻辑最清晰直观位运算 XOR成对抵消、仅剩缺失值$O(n)$$O(1)$是面试最优解兼顾时间与空间数学求和期望和减实际和$O(n)$$O(1)$是无位运算偏好的语言从仓库 hints/missing-number.md 的建议来看本题的目标是达到$O(n)$ 时间、$O(1)$ 空间即 XOR 与数学求和两种方案。它们不需要任何额外数据结构是面试与竞赛场景下的首选排序方案胜在直观哈希集合方案胜在思路通用都是理解进阶解法之前的重要铺垫。延伸阅读本题的思想可迁移到仓库内多道相关题目articles/find-all-numbers-disappeared-in-an-array.md[1, n]范围内可能出现多个缺失数字需借助下标标记技巧。articles/set-mismatch.md在一个缺失 一个重复的场景下XOR 与数学技巧依然适用。articles/first-missing-positive.md在任意数组中找第一个缺失正整数将值 ↔ 下标映射发挥到极致。articles/missing-element-in-sorted-array.md 与 articles/missing-number-in-arithmetic-progression.md在有序或等差背景下用二分查找定位缺失元素。阅读时建议对照各语言目录下的0268-missing-number.*文件如 c/0268-missing-number.c、typescript/0268-missing-number.ts、ruby/0268-missing-number.rb体会同一算法在不同语言生态中的惯用写法从而真正把思路内化为代码。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考