#347 Top K Frequent Elements

學會 heap，就是在裡面排序

Given an array of integers numbers and a number k, find the k most frequent numbers in the array. Here, k represents the number of elements that should be returned, which are the ones that appear the most frequently. The order of the result does not matter.

Input

• numbers: number[]: An array of integers

• k: An integer

Examples

Input: numbers = [4,4,4,6,6,5,5,5], k = 2Output: [4,5]
Explanation: The two most frequent numbers are 4 and 5, as they appear the most often in the array.

Input: numbers = [7,7,7,8,8,9,9,9], k = 3Output: [7,9,8]
Explanation: The three most frequent numbers are 7, 9, and 8.

Input: numbers = [10,10,10,10,10], k = 1Output: [10]
Explanation: Since there is only one unique number, 10, it is the most frequent.

如何解

[4,4,4,6,6,5,5,5]

• 先把算好的放到 map {4: 3, 6:2, 5:3}

• 有一個 heap 最左邊都是出現最多次的 []

• 要如何確保以上這件事就是每一次值放近來都要 sort 一次

function mostCommonElements(numbers, k) {
  // [4,4,4,6,6,5,5,5]
  // put num to map {4: 3, 6: 2}, key is num and value is count
  // Object.values to []
  // sort []
  let len = numbers.length;
  let lookup = new Map();
  for (let i = 0; i < len; i++) {
    lookup.set(numbers[i], (lookup.get(numbers[i]) || 0) + 1);
  }
  const comp = (a, b) => {
    return lookup.get(b) - lookup.get(a);
  };
  const heap = []; //
  lookup.forEach((v, k) => {
    heap.push(k);
    heap.sort(comp);
  });

  return heap.slice(0, k);
}