The title

Enter the integer array arr to find the smallest k number. For example, if you enter 4, 5, 1, 6, 2, 7, 3, and 8, the smallest four digits are 1, 2, 3, and 4.

Example 1:

Input: arr = [3,2,1], k = 2 output: [1,2] or [2,1]Copy the code

Example 2:

Input: arr = [0,1,2,1], k = 1Copy the code

Limitations:

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
Copy the code

Solution one: array sort

var getLeastNumbers = function(arr, k) {
     return arr.sort((a, b) = > a - b).slice(0, k)
}
Copy the code

Extension: “Dark history” of sort()

Before version 7.0 of the V8 engine, array.prototype.sort () used insert sort when the Array length was less than 10, and quicksort otherwise.

Quicksort was abandoned after V8 7.0 because it was not a stable sorting algorithm and in the worst case time complexity was degraded to O(n2).

Instead, a hybrid sorting algorithm is used: TimSort(named after a person).

Insert sort is used in small subarrays, and then merge sort is used to merge the ordered subarrays.

Solution two: build a big Top heap to solve the Top K problem

This can be solved by constructing a big top heap, where any node on the big top heap must be greater than or equal to its left and right child nodes, i.e., the top of the heap is the maximum.

So we can take k elements out of the array to make a big top heap, and then compare the rest to the big top heap, replace the top if it’s smaller than the top, and then heapize. After all the elements are iterated, the first k elements in the heap are the minimum values

Ideas:

  • Take the front of the arraykThe number (0 到 k-1Bit), construct a large top heap
  • fromkBits start iterating through the number group, and each data is compared with the top element of the big top heap. If it is larger than the top element, no processing is done and the next element is iterated. If it is smaller than the top of the heap, the element is replaced with the top of the heap, and then heaped into a large top heap.
  • Once the traversal is complete, the data in the heap is as small as the first K
var getLeastNumbers = function(arr, k) {
  // Get the first k numbers from arR and build a big top heap
  let heap = arr.slice(0, k)
  // Heap array subscripts start at 1,null is used as placeholders
  heap.unshift(null)
  buildHeap(heap, k)
  // Start with k bits
  for(let i = k; i < arr.length; i++) {
      if(heap[1] > arr[i]) {
          // Replace and heap
          heap[1] = arr[i]
          heapify(heap, k, 1)}}// Remove the first placeholder element
  heap.shift()
  return heap
};

// Build the heap in situ, from back to front, top-down
let buildHeap = (arr, k) = > {
  if(k === 1) return
  // From the last non-leaf node, top-down heap
  for(let i = k >> 1; i > 0 ; i--) {
      heapify(arr, k, i)
  }
}

/ / heap
let heapify = (arr, k, i) = > {
  // Top-down heap
  while(true) {
      let maxIndex = i
      if(2*i <= k && arr[2*i] > arr[i]) {
          maxIndex = 2 * i
      }
      if(2*i+1 <= k && arr[2*i+1] > arr[maxIndex]) {
          maxIndex = 2 * i + 1
      }
      if(maxIndex ! == i) { swap(arr, i, maxIndex) i = maxIndex }else {
          break}}}/ / exchange
let swap = (arr, i , j) = > {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}
Copy the code