448. Find All Numbers Disappeared in an Array

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:

Input: nums = [1,1]
Output: [2]

TC: O(n), SC: O(n)  
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // bulid map
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            map.put(nums[i],1);
        }
        // check
        List<Integer> ans=new ArrayList<>();
        for(int i=1;i<=nums.length;i++){
            if(!map.containsKey(i)){
                ans.add(i);
            }
        }
        return ans;
    }
}

• in-place

use - to mark, skip all already marked number
[4,3,2,7,8,2,3,1]

4: mark index 4 to -
[4,3,2,-7,8,2,3,1]
…

1: mark index 1 to -
[-4,-3,-2,-7,8,2,-3,-1]

TC: O(n), SC: O(1)

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

287. Find the Duplicate Number

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)