leetcode-cn.com/problems/to…

Answer:

  1. This problem can be solved using a heap, which takes advantage of the heap’s ability to quickly insert and retrieve elements and always sort them as required.
  2. Create a large top heap with the elements sorted in order of occurrence.
  3. Iterate over the number group, and count the frequency of occurrence of all elements.
  4. The frequency is stored in the heap with the elements, and after all the elements have been inserted, they are sorted as required.
  5. Take the top element from the heap k times and return it, and the heap remains in order from largest to smallest after each fetch.
/ * * *@param {number[]} nums
 * @param {number} k
 * @return {number[]}* /
var topKFrequent = function (nums, k) {
  let result = []; // Store the result
  let map = new Map(a);// Is used to count the occurrence frequency of elements
  // Use the heap to sort the elements in order of occurrence
  let heap = new BinaryHeap((a, b) = > b[1] - a[1]);

  // Iterate over the number group, count the occurrence frequency of the element, and store it in the Map
  for (let i = 0; i < nums.length; i++) {
    map.has(nums[i])
      ? map.set(nums[i], map.get(nums[i]) + 1)
      : map.set(nums[i], 1);
  }

  // Take out the calculated elements and their frequencies and insert them into the heap for sorting
  for (const element of map) {
    heap.insert(element);
  }

  // Retrieve k elements from the heap and store the result
  for (let i = 0; i < k; i++) {
    result.push(heap.deleteHead()[0]);
  }

  return result;
};

class BinaryHeap {
  constructor(compare) {
    this.data = []; // Use arrays to store the heap
    this.compare = compare; // The sorting function of the heap elements
  }

  // Get the number of elements in the heap
  size() {
    return this.data.length;
  }

  // Insert multiple elements into the heap
  insertMultiple(arr) {
    for (let i = 0; i < arr.length; i++) {
      this.insert(arr[i]); }}// Insert elements into the heap
  insert(value) {
    this.insertAt(this.data.length, value);
  }

  // Insert the element into the index position
  insertAt(index, value) {
    // Insert the element at the specified position
    this.data[index] = value;
    let fatherIndex = index;
    // Compare the current node with its parent and swap them if the current node is smaller
    Math.floor((index-1) / 2) is the index of the parent node in the array
    while (
      index > 0 &&
      // Use compare to compare sizes
      this.compare(
        value,
        this.data[(fatherIndex = Math.floor((index - 1) / 2)) ","0
    ) {
      // Move the parent node to the current location
      this.data[index] = this.data[fatherIndex];
      // Move the inserted value to the parent node
      this.data[fatherIndex] = value;
      // Update index to parent index, continue the next loopindex = fatherIndex; }}// Delete the largest node
  deleteHead() {
    return this.delete(0);
  }

  // Remove the element at the specified position
  delete(index) {
    // If the heap is empty, no deletion is performed
    if (this.data.length === 0) {
      return;
    }

    let value = this.data[index]; // Cache of elements to be deleted
    let parent = index; // Start with the current element and sort down the heap

    // The parent node is replaced with the larger child node after the compare method
    while (parent < this.data.length) {
      let left = parent * 2 + 1; // Index of the left child node
      let right = parent * 2 + 2; // Index of the right child node

      // There is no left child node, indicating that the current node is the last node
      if (left >= this.data.length) {
        break;
      }

      // If there is no right child node, the left child node can be brought forward to the parent node
      // The left child is the last node
      if (right >= this.data.length) {
        this.data[parent] = this.data[left];
        parent = left;
        break;
      }

      // Use the compare method to compare the size of the left and right child nodes
      if (this.compare(this.data[left], this.data[right]) < 0) {
        // Since the deleted node is already saved, you only need to copy the child node to the current parent node
        this.data[parent] = this.data[left];
        // Move the parent pointer to the child node for the next collation
        parent = left;
      } else {
        this.data[parent] = this.data[right]; parent = right; }}// Check whether the last empty space is the last leaf node
    if (parent < this.data.length - 1) {
      // If you have not collated to the leaf node, continue collating
      this.insertAt(parent, this.data.pop());
    } else {
      // When the collation is complete, the last node is more than one element
      this.data.pop();
    }

    // Returns the deleted element
    return value;
  }

  // Read the top element of the heap
  peek() {
    return this.data[0];
  }

  // Read all heap elements
  getData() {
    return this.data; }}Copy the code