题目描述

​ 题目url：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/

​ 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6] 。

解释：数组nums的长度是8，正常情况nums中的元素是1~8,而nums中缺少了5,6两个数。

示例 2：

输入：nums = [1,1] 输出：[2]

解释：nums数组只有两个2，正常范围是1~2，缺少2

题目分析

​ 创建一个新数组newArr,其长度和就数组nums一样。从旧数组第一个元素开始取出元素值numVal=nums[i]（i从0开始）。再把新数组newArr重点第numVal个的元素值赋值为1。一轮循环后新数组的第j个元素是0，就代表这个j是旧数组中缺少的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
             旧数组 nums = [4,3,2,7,8,2,3,1]   新数组 newArr = [0,0,0,0,0,0,0,0]
for循环nums中第一个元素  nums[0] = 4 
				把newArr中第4个元素赋值为1    ----->    newArr = [0,0,0,1,0,0,0,0]
				
for循环nums中第二个元素  nums[1] = 3 		
				把newArr中第3个元素赋值为1    ----->    newArr = [0,0,1,1,0,0,0,0]
				
for循环nums中第三个元素  nums[2] = 2 	
				把newArr中第2个元素赋值为1    ----->    newArr = [0,1,1,1,0,0,0,0]
				
for循环nums中第四个元素  nums[3] = 7 				
				把newArr中第7个元素赋值为1    ----->    newArr = [0,1,1,1,0,0,1,0]
				
for循环nums中第五个元素  nums[4] = 8 				
				把newArr中第8个元素赋值为1   把newArr中第2个元素赋值为1
				
for循环nums中第六个元素  nums[5] = 2 					
把newArr中第2个元素赋值为1，此时newArr的第二个已经赋值，2是nums中重复的元素，newArr不变
										   ----->    newArr = [0,1,1,1,0,0,1,1]
										   
for循环nums中第七个元素  nums[6] = 3										   
把newArr中第3个元素赋值为1，此时newArr的第三个已经赋值，2是nums中重复的元素，newArr不变													   ----->    newArr = [0,1,1,1,0,0,1,1]

for循环nums中第八个元素  nums[7] = 1
				把newArr中第1个元素赋值为1     ----->    newArr = [1,1,1,1,0,0,1,1]
循环结束后，newArr中第x个位置上元素是0，则x就是旧数组nums中缺失的元素。是第5个和第6个缺失

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public static List<Integer>  findDisappearedNumber1(int[] nums) { 
	ArrayList<Integer> listResult= new ArrayList<>();
       int[] newArr = new int[nums.length];
       for (int i = 0; i < nums.length; i++) {
           newArr[nums[i] -1] = 1; //newArr中第nums[i]个元素对应的下标是nums[i]-1
       }
       for(int j =0; j < newArr.length; j++) {
           if(newArr[j] == 0) {
               listResult.add(j+1);
           }
       }
       return listResult;
   }

参考答案

​ 思路是从0开始遍历数组nums，下标i的范围是[0，nums.length-1]。找出nums[i]在 在区间 【1，n】 内对应下标。比如nums[i]=4—>4对应的下标是3.让3号下标的元素变成负数。代表nums[i]出现过一次。for循环结束nums中哪个位置x元素>0,说明x+1是缺失的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

* 原数组    [4,3,2,7,8,2,3,1]
* 理想数组   [1,2,3,4,5,6,7,8]     	
* 找出nums[i]在理想数组中的下标index
* 再原数组下标是index的元素变成负数    
* 那么元素和其小标有关系   nums[i]=i+1
*  元素        对应的索引                                 新数组
*    4       3: 把3号索引的元素改成负数(7--->-7)     {4,3,2,-7,8,2,3,1}
*    3       2: 把2号索引的元素改成负数(2--->-2)     {4,3,-2,-7,8,2,3,1}
*    2       1: 把1号索引的元素改成负数(3--->-3)     {4,-3,-2,-7,8,2,3,1}
*    7       6: 把6号索引的元素改成负数(3--->-3)     {4,-3,-2,-7,8,2,-3,1}
*    8       7: 把7号索引的元素改成负数(1--->-1)     {4,-3,-2,-7,8,2,-3,-1}
*    2       1: 此时 nums[1]=-3; 又因为num取了绝对值，又变成+3，在变成-3
*    3       2: 已经改过
*    1       0: 把0号索引的值改为负数(4--->-4)       {-4,-3,-2,-7,8,2,-3,-1}
*    此时没有变成负数的索引是4、5，对应的值是5，6。

   
    public static List<Integer> findDisappearedNumber2(int[] nums) {
        List<Integer> missList=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            int num=Math.abs(nums[i]);
            int index=num-1; //元素对应的索引  4--->3
            if(nums[index]>0) {
                nums[index] = -nums[index];
            }
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                missList.add(i+1);
            }
        }
        return missList;
    }

参考答案图解

avatar

avatar

avatar

对比总结

​ 我的想法是用一个新的数组newArr【newArr的长度与旧数组相同】，在newArr中记录原数组的某个元素是否出现过，若出现让newArr对应下标的元素变成1.【比如 4在newArr中对应下标是3，就让newArr[3] =1 】。和参考代码相比我多创建了一个数组，多占用了一些栈内存。而参考答案只用了最原始的数组nums[],在nums[]中标记为负数。理想的数组ideaNums是不存在的【ideaNums的特点是从1到n的递增数列，每次+1】就可以用一个变量表示，节省了栈空间但是增加了逻辑复杂度。