DaleStudy | Leetcode Study 1주차 - Top K Frequent Elements

Leetcode Study

문제

Given an integer array nunmsand an integer k, return the kmost frequest elements. You may return the answer in any order.

 

Example 1:

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

 

Example 2:

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

 

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• kis in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer in unique.

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

 

풀이

 

이 문제는 배열에서 가장 빈번하게 나오는 숫자 k개 골라 배열로 리턴하는 문제이다. 일단 나는 알고리즘 문제를 접할 때, 가장 빈번하게든지 등의 정보를 저장해야하는 일이 있다면, 객체를 저장하는 것을 생각하는 편이다. 그리고 단계를 나눠서 생각하는 것이 중요하다.

1. 먼저 Map을 이용해서 원소의 갯수가 몇 개인지 저장한다.
2. 그 정보를 기반으로 가장 빈번하게 나온 순서대로 정렬을 시킨다.
3. 마지막으로 k만큼 자른 뒤에 그 키 값을 리턴하면 끝난다. 

function topKFrequent(nums: number[], k: number): number[] {
    const frequentMap = new Map<number, number>();

    for (const num of nums) {
        frequentMap.set(num, (frequentMap.get(num) ?? 0) + 1);
    }

    const sorted = Array.from(frequentMap.entries())
    .sort((a, b) => b[1] - a[1]);

    return sorted.slice(0, k).map(([key]) => Number(key))
};

 

이렇게 풀면 O(n)의 시간복잡도와 O(n)의 공간복잡도를 가지게 된다. 

 

 

 

 

Link: https://leetcode.com/problems/top-k-frequent-elements/description/