FindAllNumbersDisappearedInAnArray [source code]

public class FindAllNumbersDisappearedInAnArray {
    public List<Integer> findAllNumbersDisappearedInAnArray(int[] nums) {
        int[] count = new int[nums.length];
        Arrays.fill(count, -1);
        for (int i = 0; i < nums.length; i++) count[nums[i] - 1]++;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (count[i] < 0) res.add(i + 1);
        }
        return res;
    }

    public static void main(String[] args) {
        FindAllNumbersDisappearedInAnArray tester = new FindAllNumbersDisappearedInAnArray();
        int[] input1 = {4,3,2,7,8,2,3,1};
        for (int i : tester.findAllNumbersDisappearedInAnArray(input1)) System.out.println(i);
        System.out.println("Finish");
    }
}

这种所有的element都处于[1,n]的array，是摆明了让你用array替代map的；
这题一个比较难的要求是no extra space。这种要求好像还是比较难以做到的。但是却是经常出现；
linear time这个我们已经见过几次了，目前一个主流的思路就是利用additional data structure来保存每一个iteration的信息就行了；
但是no extra space这个有没有什么常规套路，目前还没有总结到；

前面我们已经讲过了，拿到一个问题没思路怎么办？先从最蠢的做法开始做。
no extra space这个目前想到的一个思路是，要么直接利用input space，也就是nums进行处理（return list本身也不算extra space,不过这里好像没有什么用过）；

TODO:
no extra space requirement;
res.add不知道最后出来的顺序对不对？linked list的添加顺序好像是加在head？如果不行，或许try append?

这个算法的速度是16ms, 78%, 还算可以接受吧.

Problem Description

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:

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

Output:
[5,6]
Subscribe to see which companies asked this question.

Hide Tags Array
Hide Similar Problems (H) First Missing Positive