给定一个包含 [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
中的所有数字都 独一无二
进阶:你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
Related Topics
位运算数组哈希表数学排序 👍 579👎 0
异或、求和 & 【看起来没人用的其实也能用的 原地交换 !!】
都知道的异或、求和先贴下、其他还有哈希表,重构数组遍历等等,没啥好说的了,大家都看很多遍了
异或
class Solution {
public int missingNumber(int[] nums) {
int num = 0;
for (int i = 0; i < nums.length; i++) {
num ^= nums[i];
num ^= i;
}
num ^= nums.length;
return num;
}
}
求和
class Solution {
public int missingNumber(int[] nums) {
int num = 0;
for (int i = 0; i < nums.length; i++) {
num -= nums[i];
num += i;
}
num += nums.length;
return num;
}
}
丢失数字之类的还有一种会用到原地交换的解法
这里我们其实也可以尝试下。大促晚值班摸鱼,来玩点花样
原地交换
跟官方题解写一样缺少乐趣,毕竟是简单题,能玩的花样一遍都比较多,
拿官方例题来分析下,第一行对应为数组下标,第二行数原始数组,
- 如果
nums[i] == nums.length
原地交换会越界,那么我就声明一个变量用来保存存放在这个位置的数字,这样我们就可以顺利使用原地交换了,毕竟要求时间O(n)
,空间O(1)
- 其实你也可以声明一个长度为
nums.length+1
的数组来处理,这样可以省事,不过空间就不是O(1)
了
- 原来第
n
位上的数字不存在,那就在代码里用-1
表示,图里用x
表示 - 从0下标开始交换,把0交换给n,此时记录丢失数字为0 ,
missing = 0;
- 后面从下标1开始交换,一直交换这些比较简单省略,直到到下标1上的值为
x
了,记录当前丢失数字missing = 1;
- 后面继续交换,直到最后下标8上的值为
x
,记录missing = 8;
- 结束
同时,看下剑指offer03的数组中的重复数字这题,试着用原地交换的方法来理解下,或许对你能有帮助
【原地交换】图解,看个明白
原地交换代码
class Solution {
public int missingNumber(int[] nums) {
//丢失的
int misssing = nums.length;
//额外占用的第nums.length下标位
int n = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i]==nums.length){
n = nums[i];
nums[i] = -1;
}
while (nums[i] != -1 && nums[i] != i ){
swap(nums,i,nums[i]);
if (nums[i]==nums.length){
n = nums[i];
nums[i] = -1;
}
}
if (nums[i]==-1){
misssing = i;
}
}
return misssing;
}
public void swap(int[] nums, int x, int y){
int tmp = nums[x];
nums[x] = nums[y];
nums[y] = tmp;
}
}