leetcode-cn.com/problems/zu…

Answer:

  1. The problem doesn’t require the results to be sorted, so you can use the idea of quicksort.
  2. Quicksort constantly splits the array in half around a value, with the smaller value on the left and the larger value 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[]} arr
 * @param {number} k
 * @return {number[]}* /
var getLeastNumbers = function(arr, k) {
  return quickSort(arr, 0, arr.length - 1, k)
};

const quickSort = (nums, left, right, k) = > {
  // If nums is less than or equal to 1, it is returned as the result without sorting
  if (nums.length <= 1) return nums;

  // 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) {
      return nums.slice(0, k)
    }

    // 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, return the first k elements
  return nums.slice(0, k)
};

const partition = (nums, left, right) = > {
  let pivot = left; // With the median value left, everything smaller 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 smaller 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 value is less than nums[pivot], move it to the index position
    if (nums[i] < nums[pivot]) {
      // 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 a value less than NUMs [pivot], while NUMs [pivot] remains in place
  // Switch the two, and the median is moved to index, where the value to the left is smaller than it
  [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