Leetcode 442) Find All Duplicates in an Array

20 May 2021 in Algorithms

• in place로 풀기 위해서, 인덱스를 활용한다.
  • 2라는 숫자가 어레이에 나오면, index = 1인 원소를 음수 처리 해준다. (1부터 시작이라서)
  • Constraints 에서 숫자 값이 양수기 때무에 가능. 만약 음수도 있다면, 이 방법 사용하지 못한다.

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

        for(int i =0;i<nums.length;i++){
            int x = Math.abs(nums[i]);
            if(nums[x-1]<0){
                lst.add(x);
            }
            nums[x-1] = -nums[x-1];
        }        
        return lst;
    }
}

다른 풀이

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

        for(int i =0;i<nums.length;i++){
            if(nums[Math.abs(nums[i])-1]<0){
                lst.add(Math.abs(nums[i]));
            }
            nums[Math.abs(nums[i])-1] = -nums[Math.abs(nums[i])-1];
        }        
        return lst;
    }
}