DEV Community
·
LeetCode 思考：缺失的数字
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定一个包含n个不同数字的数组nums，范围为[0, n]，可以通过计算范围内所有数字的总和减去数组的总和来找到缺失的数字。使用异或操作可以更高效地解决此问题，时间复杂度为O(n)，空间复杂度为O(1)。
🎯
关键要点
- 给定一个包含n个不同数字的数组nums，范围为[0, n]，返回缺失的数字。
- 示例输入：nums = [3, 0, 1]，输出：2。
- 可以通过计算范围内所有数字的总和减去数组的总和来找到缺失的数字。
- 使用reduce函数可以计算总和，但时间复杂度为O(n)，空间复杂度为O(n)。
- 使用异或操作可以更高效地解决此问题，时间复杂度为O(n)，空间复杂度为O(1)。
- 异或操作的特性是相同的数字异或结果为0，不同的数字异或结果为1。
- 初始化结果为nums.length，以处理缺失数字等于nums.length的情况。
- 最终结果是缺失的数字，通过遍历数组进行异或操作得到。
❓
延伸问答
如何找到缺失的数字？
可以通过计算范围内所有数字的总和减去数组的总和来找到缺失的数字。
使用异或操作有什么优势？
使用异或操作可以更高效地解决问题，时间复杂度为O(n)，空间复杂度为O(1)。
给定数组[3, 0, 1]，缺失的数字是什么？
缺失的数字是2。
如何使用reduce函数计算总和？
可以使用reduce函数对数组进行求和，但时间复杂度为O(n)，空间复杂度为O(n)。
异或操作的特性是什么？
异或操作的特性是相同的数字异或结果为0，不同的数字异或结果为1。
如何处理缺失数字等于数组长度的情况？
可以通过初始化结果为nums.length来处理这种情况。
➡️
