[B] [C] [D]

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

The question is very simple, so we don’t have to say much more, and we’ll just look at the problem

Solution 1: Sorting & interception

Sort first and slice the first K elements

The code is as follows:

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

Solution 2: K minimum values before big top heap maintenance

  1. Because of the maintenance beforekSo, first you need to write a big top heap, so that every time something smaller than the top element is inserted into the heap, then the top element is popped out
  2. Create a large top heap instance that loops through the elements of an array when there are not enough in the heapkInserts the current value into the heap when the current value is smaller than the top element

The code is as follows:

Class BigHeap {constructor(k){this.arr = []; this.size = 0; this.max = k; } // Insert operation push(val){this.arr.push(val); this.size++; if(this.size>1){ let cur = this.size-1, parent = (cur-1)>>1; while(cur>0&&this.arr[cur]>this.arr[parent]){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent,parent = (cur-1)>>1; } } if(this.size>this.max) this.pop(); } pop(){this.arr[0] = this.arr.pop(); this.size--; let cur = 0, childl = 1,childr = 2; while( (childl<this.size&&this.arr[childl]>this.arr[cur]) || (childr<this.size&&this.arr[childr]>this.arr[cur]) ){ if(childr<this.size&&this.arr[childr]>this.arr[childl]){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr; }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]] cur = childl; } childl = cur*2+1,childr = cur*2+2; Top (){return this.arr[0]}} var getLeastNumbers = function(arr, k) {if(k===0) return []; // Create a big top heap instance const heap = new BigHeap(k); // loop array elements for(let I = 0; i<arr.length; I++) {if (heap size < k | | arr [I] < heap. The heap top ()). Push (arr) [I]} / / return of k kept in a pile of digital return heap. Arr. };Copy the code

At this point we are done with leetcode- finger Offer 40- the minimum number of k

If you have any questions or suggestions, please leave a comment!