leetcode 448 Find All Numbers Disappeared in an Array [JAVA]

리뷰

• 1~n의 값을 넣은 list를 만든 후, 제시된 배열을 순회하는 반복문을 돌리고 list.contains()를 사용해 배열값의 포함 여부를 확인했다. 시간 초과 문제가 발생했고 이를 해결하기 위해 HashSet과 카운팅정렬로 다시 풀어보았다.

 

시간초과 : list.contains()사용  ---> 22ms : set.contains()사용  ---> 3ms : 카운팅 정렬

 

공부한 것

• 작은 범위의 정수를 정렬할 땐 카운팅 정렬을 고려하자. 

 

• HashSet vs 카운팅 정렬 속도차이 

 

[gpt]  두 알고리즘 모두 시간 복잡도가 O(N)입니다. 시간 복잡도가 같다고 해도, 실제로 실행 속도는 알고리즘의 구현 방식과 데이터 구조, 환경 등에 따라 달라질 수 있습니다. 

카운팅 정렬이 더 빠른 이유는 다음과 같습니다:

메모리 접근 속도: 카운팅 정렬은 메모리 상에 연속된 위치에 접근하여 데이터를 처리하므로 CPU의 캐시 메모리를 효율적으로 활용할 수 있습니다. 이는 데이터 접근 속도를 빠르게 만듭니다.

연산의 단순성: 카운팅 정렬은 각 숫자의 등장 횟수를 직접 카운트하고, 이를 바탕으로 결과를 생성하는 단순한 연산을 수행합니다. 반면 HashSet은 해시 함수와 충돌 해결 등의 복잡한 내부 처리 과정이 필요합니다.

따라서 정수 배열에 대해서는 카운팅 정렬이 보다 빠른 속도를 보이며, 일반적으로 HashSet을 사용한 방법보다 시간 효율성이 높습니다.

 

문제

448. Find All Numbers Disappeared in an Array
Solved
Easy
Topics
Companies
Hint
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]
 

Constraints:

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
 

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

 

내 답안

1. time over - list.contains()

//time over
public List<Integer> findDisappearedNumbers(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
    for(int i=1; i<=nums.length; i++){list.add(i);}
    for(int k : nums){if(list.contains(k)){list.remove(Integer.valueOf(k));}}
    return list;
    }
    }

 

2. 22ms - set.contains()

    //22ms - set.contains()
    class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for(int i=1; i<=nums.length; i++){set.add(i);}
    for(int k : nums){if(set.contains(k)){set.remove(k);}}
    ArrayList<Integer> list = new ArrayList<>(set);
    return list;
    }
}

 

3. 3ms - 카운팅 정렬

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        int result[] = new int[nums.length+1];
        for(int i=0; i<nums.length; i++){result[nums[i]]++;}
        for(int i=0; i<nums.length+1; i++){if(result[i]==0&&i!=0){list.add(i);}}
        return list;
    }
}