448 Find All Numbers Disappeared in an Array

448. Find All Numbers Disappeared in an Array

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]

分析&代码

和442一样，可以用i-1来标记是否访问过，然后two pass做，第一个pass统计存在的元素，如果有就标记为负数，第二个pass遇到不是负数的位置，就把这个index + 1记录到答案里

    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int len = nums.length;
        if(len == 0) {
            return res;
        }
        for(int i = 0; i < len; i++) {
            int index = Math.abs(nums[i]) - 1;
            if(nums[index] > 0) {
                nums[index] = -nums[index];
            } 
        }
        for(int i = 0; i < len; i++) {
            if(nums[i] > 0) {
                res.add(i + 1);
            }
        }
        return res;
    }

显然也是O(2n) => O(n)