Original link: leetcode-cn.com/problems/to…

Answer:

  1. The problem doesn’t require the results to be sorted, so you can use the idea of quicksort.
  2. Quicksort is used to divide the array in half at each recursion, centered around a value, with frequencies greater on the left and smaller on the right. For this problem, we only need to move k elements to the top half of the array.
  3. You can use the quicksort code template directly, and when recursing, you just need to scroll down to the side where K is, and you can speed up the sorting process.
  4. After sorting, the first k elements of the array are the result and can be returned directly.
/ * * *@param {number[]} nums
 * @param {number} k
 * @return {number[]}* /
var topKFrequent = function (nums, k) {
  let map = new Map(a);// Use Map to record the frequency of all numbers

  // Iterate over the number group, record the occurrence frequency of each number and save it in Map
  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i])) {
      map.set(nums[i], map.get(nums[i]) + 1);
    } else {
      map.set(nums[i], 1); }}// Convert the relationship between numbers and frequencies into an array for sorting.
  const numsWithFrequency = [...map.entries()];

  // Use quicksort to sort the array from largest to smallest in frequency and return the first k digits
  return quickSort(numsWithFrequency, 0, numsWithFrequency.length - 1, k);
};

const quickSort = (nums, left, right, k) = > {
  // If the length of nums is less than or equal to 1, no sorting is required
  if (nums.length <= 1) return nums.map(([num]) = > num);

  // If nums has length, it needs to sort
  if (left < right) {
    // Divide nums from left to right into two segments, where the median value is pivot
    // The value on the left side of pivot is less than nums[pivot], and the value on the right side of pivot is greater than nums[pivot].
    const pivot = partition(nums, left, right);

    // If pivot is exactly k, the sorting is done ahead of time, and the result can be returned directly
    if (pivot === k) {
      // Returns the first k elements as numbers
      return nums.slice(0, k).map(([num]) = > num);
    }

    // Press pivot to split the NUMs into two ends and sort them separately. Since the array is not completely sorted, only the first K elements need to be sorted to one side
    // Since we do not know the relationship between pivot and k in advance, we need to recurse according to the position of k
    pivot > k
      ? quickSort(nums, left, pivot - 1, k)
      : quickSort(nums, pivot + 1, right, k);
  }

  // After sorting, convert the first k elements to numbers
  return nums.slice(0, k).map(([num]) = > num);
};

const partition = (nums, left, right) = > {
  let pivot = left; // With the median value left, everything larger than it is placed to its left and everything larger than it is placed to its right
  let index = left + 1; // The array is traversed from left+1, with index indicating where values with frequencies greater than nums[pivot] are stored

  // Iterate over the elements from left+1 to right, splitting them in half with nums[pivot] as the median
  for (let i = index; i <= right; i++) {
    // If the current frequency is greater than nums[pivot], move it to index
    if (nums[i][1] > nums[pivot][1]) {
      // Set nums[I] to nums[index]
      [nums[i], nums[index]] = [nums[index], nums[i]];
      // Move index one bit to store the next valueindex++; }}// The index has been moved one more bit when the loop is complete
  index--;
  // When the loop stops, the index position stores values with frequencies greater than NUMs [pivot], while NUMs [pivot] remains in place
  // Switch the two, and the median is moved to the index position with a greater frequency to the left
  [nums[pivot], nums[index]] = [nums[index], nums[pivot]];

  // The new median is returned, and the lower level recursively splits the array into two segments to continue sorting
  return index;
};
Copy the code