347. Top K Frequent Elements

💡 풀이

// Sorting - O(NlogN)
var topKFrequent = function (nums, k) {
  let obj = {};

  for (let i = 0; i < nums.length; i++) {
    if (!obj[nums[i]]) obj[nums[i]] = 1;
    else obj[nums[i]]++;
  }

  let keys = Object.keys(obj);
  let sorted = keys.sort((a, b) => obj[b] - obj[a]);
  sorted = sorted.map(num => Number(num));

  let answer = sorted.slice(0, k);
  // console.log(answer);
  return answer;
};

// No sorting
var topKFrequent = function (nums, k) {
  const freqMap = new Map();
  const bucket = [];
  const result = [];

  for (let num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }

  for (let [num, freq] of freqMap) {
    bucket[freq] = (bucket[freq] || new Set()).add(num);
  }

  for (let i = bucket.length - 1; i >= 0; i--) {
    if (bucket[i]) result.push(...bucket[i]);
    if (result.length === k) break;
  }
  return result;
};

📝 결과

📝 정리

유사 문제: https://velog.io/@ken1204/692.-Top-K-Frequent-Words

바로 이전에 풀었던 문제와 매우 유사하다. 중요한 부분은 정렬 없이 구현한 아래 방법인데, 이 방법의 시간 복잡도는 O(N)이다. 아직 아래 방법은 확실히 이해가 안되서 설명은 나중에 이해가 됐을 때 추가 작성할 예정이다!

나는 위의 방법(정렬)으로 풀었는데, 문제 풀이 과정은 유사 문제에 있는 과정과 같다.

수정, 지적을 환영합니다!

문제 링크

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

LeetCode GitHub

https://github.com/tTab1204/LeetCode