【Leetcode】 448. Find All Numbers Disappeared in an Array

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]

Solution

public List<Integer> findDisappearedNumbers(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        List<Integer> list = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return list;
        }
        if (nums[0] > 1) {
            for (int n = 1; n < nums[0]; n++) {
                list.add(n);
            }
        }
        for (int i = 0; i < len - 1; i++) {
            if (nums[i] < nums[i + 1]) {
                if (nums[i + 1] - nums[i] > 1) {
                    for (int j = nums[i] + 1; j < nums[i + 1]; j++) {
                        list.add(j);
                    }
                }
            }
        }
        if (nums[len - 1] < len) {
            for (int m = nums[len - 1] + 1; m <= len; m++) {
                list.add(m);
            }
        }
        return list;
    }

Result

Analyse

思路还是一个数一个数的比较，但是很容易出现特殊情况没有考虑到，其实不适合bug free的写法，因为边界需要特殊的再标注。

Optimization

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

Idea

这个思路很好，其实按照Description来说，应该就是1， 2， 3， 4， …. n的一个排序，所以每次根据num[i]来找对应的index，中间也就就相差了1，将index对应的数字取反，那样就相当于有了一个标志了，这里要注意，可能后面的次序对应的i已经被取反，但这个index存的数还是有意义，所以要使用Math.abs来操作。然后最后进行一次判断是否大于0，说明这个index对应的没有被取，拿出来就好了。