[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
- Because of the maintenance before
k
So, 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 - Create a large top heap instance that loops through the elements of an array when there are not enough in the heap
k
Inserts 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!