[leetcode]Top K Frequent Elements

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

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {

    // map 초기화
    const numMap = new Map();
    for(let i =0;i < nums.length; i++){
        if(!numMap.get(nums[i])){
            numMap.set(Number(nums[i]),1)

        }else{
           numMap.set((nums[i]),numMap.get(nums[i])+1)
        }
    }
    //map을 arr로 만들어 sort.

    const mapToArr = Array.from(numMap).sort((a,b)=>b[1]-a[1])
    console.log(mapToArr);

    //k까지 slice한다. 
    const ret = mapToArr.slice(0,k).map((el)=>el[0])
    return ret
};

코드를 좀더 다듬어 보자면

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
  // 1. 숫자별 빈도수 카운트
  const freqMap = new Map();
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
  }
  
  // 2. [숫자, 빈도수] 배열로 변환 후, 빈도수 내림차순 정렬
  const sorted = [...freqMap.entries()].sort((a, b) => b[1] - a[1]);
  
  // 3. 상위 k개 숫자만 추출
  return sorted.slice(0, k).map(([num]) => num);
};

...freqMap.entries() 를 이용해서 Array.from을 대체할수있다.

시간복잡도

1. 빈도수 세기 (for 루프 + Map)→ O(n)

2. Map → 배열 변환 (entries()) → O(n)

3. 정렬 → O(n log n)

4. slice 및 map (최대 k) → O(k) (k ≪ n이면 무시 가능)

결론:
전체 시간복잡도 = O(n log n)
(정렬 단계가 가장 큼)

공간복잡도

1. Map에 빈도 저장 → O(n)

2. 배열로 변환/정렬→ O(n)

3. 리턴용 배열→ O(k) (k≪n, 무시 가능)

결론:
전체 공간복잡도 = O(n)