[Leetcode] 448. Find All Numbers Disappeared in an Array | 找到所有数组中消失的数字

yPhantom 2020年02月03日 25次浏览

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]

这道题我是真没想出。直接看的讨论区的解答。比较精妙的一点在于题目给出了条件1 ≤ a[i] ≤ n。我觉得这是比较关键的一点,这代表a[i]能被影射为数组下标,从而得到结果。以后碰到这种条件应当往这方面想一想。

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

参考链接

Java accepted simple solution