Find All Numbers Disappeared in an Array

Posted on |

问题描述 (难度简单-448)

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

解题方法

需要在一次遍历的过程中标记已经出现过的数字，进而找出未出现的数字，只能通过自身的数组进行标记。按照上面的示例，索引位置为0的位置值为4，我们需要将4标记一下已经出现过，索性用索引位置为3的地方做标记，将对应的值取反，标记为负值。这样1-8的数组可以对应0-7的索引位置进行标记，最后未被标记为负值的元素的index加上1即为未出现过的数字。迭代的流程如下图：

cmd-markdown-logo

cmd-markdown-logo

解题代码

实践代码的过程中需要注意，遍历到的节点value值可能已经是负，已经被标记，但是还是需要根据其绝对值找到该value需要标记的index位置，这也是为什么将其标记为反数而不是其他任意负数的原因。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<Integer> findDisappearedNumbers(int[] nums) {
        ArrayList<Integer> arrayList=new ArrayList();
        //数组index对应的数值为value，将index=value的位置标记为-value，表示出现过，并且value取正可以持续标记
        for(int i=0;i<nums.length;i++){
            //已经被标记
            if(nums[i]<0) {
                if(nums[-nums[i]-1]>0){
                    nums[-nums[i]-1]=-nums[-nums[i]-1];
                }
            }else {//未被标记
                if(nums[nums[i]-1]>0){
                    nums[nums[i] - 1] = -nums[nums[i] - 1];
                }
            }
        }
        //遍历出未被标记的index，index+1即为未出现过的数值
        for (int i=0;i<nums.length;i++){
            if(nums[i]>0){
                arrayList.add(i+1);
            }
        }

        return arrayList;
    }

实际上第一个循环的处理可以更加简单清晰，用下面的循环体内容替换：

1
2
3
4
5
6
for(int i=0;i<nums.length;i++){
    int value=Math.abs(nums[i])-1;//直接取当前index位置value的绝对值
    if(nums[value] >0){
        nums[value]=-nums[value];
    }
}

总结

这道题比较难想到这个思路，并且在编码过程中思考也需要更加缜密，想清楚了再进行书写。