Leetcode 448) Find All Numbers Disappeared in an Array

20 May 2021 in Algorithms

• 추가 공간이 사용하는 코드. 별로 좋지 않다.

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        boolean[] position = new boolean[nums.length];
        for(int i=0;i<nums.length;i++){
            position[nums[i]-1]=true;
        }
        List<Integer> lst = new ArrayList<Integer>();
        for(int i=0;i<nums.length;i++){
            if(!position[i]){
                lst.add(i+1);
            }
        }
        return lst;
    }
}

다른 풀이

• 추가 공간을 사용하지 않고, index를 잘 활용해서 풀음.

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