448.找到所有数组中消失的数字

题目描述

原题
给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。
示例 1:
1
输入:nums = [4,3,2,7,8,2,3,1]
2
输出:[5,6]
Copied!
示例 2:
1
输入:nums = [1,1]
2
输出:[2]
Copied!
提示:
    n == nums.length
    1 <= n <= 105
    1 <= nums[i] <= n
进阶:你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

题解

1
class Solution {
2
public List<Integer> findDisappearedNumbers(int[] nums) {
3
//本题和剑指offer第3题很像
4
//创建一个辅助数组 0的位置放1 1的位置放2 ...n-1的位置放n最后找到为0的数组
5
int len = nums.length;
6
int[] aux = new int[len];
7
for(int i = 0;i < len ;i++){
8
aux[nums[i]-1] = nums[i];
9
}
10
List<Integer> list = new ArrayList<>();
11
for(int i = 0;i < len;i++){
12
if(aux[i]==0){
13
//获取为0的索引然后+1
14
list.add(i+1);
15
}
16
}
17
return list;
18
}
19
}
Copied!
1
//官方解法,不创建新的数组,采用原地归并的方式
2
class Solution {
3
public List<Integer> findDisappearedNumbers(int[] nums) {
4
//找到当前x然后nums[x]+n
5
//如果不存在某一个数,那么对应的nums[x]也不会+n
6
//[4,3,2,7,8,2,3,1] len = 8第一个索引为4 那么nums[3]就会+8=15
7
//3出现两次所以nums[2]位置会+2*8 = 18
8
//依次遍历的到的最终结果[12, 19, 18, 15, 8, 2, 11, 9]
9
//因为不存在5,6的值 对应的nums[4]和nums[5]也不会+8
10
int n = nums.length;
11
for (int num : nums) {
12
int x = (num - 1) % n;
13
nums[x] += n;
14
}
15
List<Integer> ret = new ArrayList<Integer>();
16
for (int i = 0; i < n; i++) {
17
if (nums[i] <= n) {
18
ret.add(i + 1);
19
}
20
}
21
return ret;
22
}
23
}
Copied!
最近更新 4mo ago
复制链接