448. Find All Numbers Disappeared in an Array - Easy

前往題目

想法

• 用個set或陣列之類的存，最後再看一遍缺了哪個
• 如果使用傳進來的nums[]不知道該怎麼做才能O(1)空間

思路

Time: O(n)
Space: O(1)

1. 疊代所有陣列中的數字，把數字當作index，標記該index的數字為負數
2. 遇到負數就跳過
3. 最後疊代一次1~n看原本的陣列裡面哪個index的數字是正數，就是缺失的數字

Code

簡易版

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        Set<Integer> set = new HashSet();

        List<Integer> res = new ArrayList<>();

        for (int e : nums) {
            set.add(e);
        }

        for (int i = 0; i < nums.length; ++i) {
            if (!set.contains(i + 1)) res.add(i + 1);
        }

        return res;
    }
}

優化空間版

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();

        for (int num : nums) {
            // Appears twice, do nothing
            if (nums[Math.abs(num) - 1] < 0) {
            } else { // Mark
                nums[Math.abs(num) - 1] *= -1;
            }
        }

        // Positive numbers are the numbers don't exist
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] > 0) res.add(i + 1);
        }

        return res;
    }
}