LeetCode 347 - Top K Frequent Elements (Medium)

문제

LeetCode - 347번

풀이 과정

배열에서 가장 많이 등장하는 k 개의 숫자를 찾아 반환하는 문제입니다.

알고리즘의 시간 복잡도를 O(NlogN) 으로 지정해놨기 때문에 Hash Map 을 사용해서 빈도수를 저장하였습니다.

우선 배열의 각 요소를 순회하며 Map 에 빈도수를 저장하는데에는 O(N) 의 시간 복잡도가 들고,
이후 빈도수를 기준으로 Map 을 정렬하면 O(NlogN) 의 시간 복잡도를 얻게 됩니다.

마지막으로 정렬 결과 k 개의 상위 요소들을 반환해주면 됩니다.

코드

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  const numberCount = new Map();

  nums.forEach((num) => {
    if (numberCount.has(num)) {
      numberCount.set(num, numberCount.get(num) + 1);
    } else {
      numberCount.set(num, 1);
    }
  });

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

  const answer = [];
  for (let i = 0; i < k; i++) {
    answer.push(sorted[i][0]);
  }

  return answer;
};