题目
给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例
示例 1
输入:nums = [3,0,1]
输出:2
解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。
示例 2
输入:nums = [0,1]
输出:2
解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2 是丢失的数字,因为它没有出现在 nums 中。
示例 3
输入:nums = [9,6,4,2,3,5,7,0,1]
输出:8
解释:n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。
示例 4
输入:nums = [0]
输出:1
解释:n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。1 是丢失的数字,因为它没有出现在 nums 中。
提示
n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二
进阶
你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
相关题目
相关链接
- 力扣(LeetCode)268.丢失的数字 — https://leetcode-cn.com/
- 力扣(LeetCode)136. 只出现一次的数字 — https://leetcode-cn.com/
- 力扣(LeetCode)287. 寻找重复数 — https://leetcode-cn.com/
- 力扣(LeetCode)41. 缺失的第一个正数 — https://leetcode-cn.com/
- 力扣(LeetCode)765. 情侣牵手 — https://leetcode-cn.com/
分析
简单类型的题目。
先把题目读清楚:
区间[0,n]一共有n+1个数,而题目中说的是 [0,n]是n个数的数组,所以只会少1个数字。
解法
解法一:排序
将数组nums进行排序,找到nums[i]!=i的位置,就是缺少的那个数。
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;
}
解法二:额外数组
由于 [0,n]是数字连续的。所以我们使用一个额外的 n+1 长度的数组 pos。将nums[i]作为pos的索引赋值为1,从1开始遍历pos数组,pos[i]==0即为少的那个数字。
public int missingNumber(int[] nums) {
int pos[] = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
pos[nums[i]] = 1;
}
for (int i = 1; i < pos.length; i++) {
if (1 != pos[i]) {
return i;
}
}
return 0;
}
解法三:数学计算
区间[0,n]是连续的数组,那么利用等差数列的性质可以算出来n个数的总和,减去nums数组中的元素,则就是少的那个数。
public int missingNumber(int[] nums) {
int n = nums.length;
int cur = 0, sum = n * (n + 1) / 2;
for (int i : nums) cur += i;
return sum - cur;
}
解法四:亦或
亦或计算使然。 a^a=0,0^a=a.
所以将 0...n 和 nums[0...n] 进行亦或计算,则计算出来的值就是缺少的那个数。
public int missingNumber(int[] nums) {
int n = nums.length;
int ans = 0;
for (int i = 0; i <= n; i++) ans ^= i;
for (int i : nums) ans ^= i;
return ans;
}
最后
期望与你一起遇见更好的自己
