Offer 40. Minimum number of k

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 = 2Output:1.2] 或者 [2.1]
Copy the code

Example 2:

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

Direct manipulation of array methods

If the ans length is greater than k, go through ans to find the index of the maximum value, and then delete the maximum value according to the index. The remaining k minimum values are as follows:

var getLeastNumbers = function(arr, k) { 
     let ans = []; 
     let index = 0; 
     for(let i = 0; i < arr.length; i ++){ 
        ans.push(arr[i]); 
        if(ans.length > k) { 
           index = getMax(ans); 
           ans.splice(index,1); }}return ans;
}; 
var getMax = function(arr){ 
    if(! arr)return []; 
    let maxVal = arr[0]; 
    let maxLeng = 0; 
    for(let i = 1; i < arr.length; i ++){ 
         if(arr[i] > maxVal) { maxVal = arr[i]; maxLeng = i; }}return maxLeng; 
 }
Copy the code

Two. Through the big top heap implementation

Heap characteristics:

  • The root number is I. Number of the left child node: 2 x I Number of the right child node: 2 x I + 1 2. An array that can be stored with contiguous controls

  • Implement with arrays

  • A heap is an implementation of a priority queue, which is an alias for a heap

  • The value of any node is the large or small top heap of all nodes of its child tree

    • In any triangle region, the root node is larger than the child node, which is also called the big top heap.
    • The root node of any triangle region is smaller than the child node, also known as the small top heap.

    Data structure definition: Define a property and maintain that property

Answer: We know that the queue is the head, and the tail team operation, because this is the minimum number of k, so we can according to the characteristics of large pile jacking, delete the root node, are small value of the stay, with each team and the team to keep big top of the heap requirements, when the team need to be adjusted upward, to maintain the characteristics of big pile jacking method is adjusted upward, Compare with the root node, if is greater than the root node is interchangeable with the root node values, in turn until the root node, the index of the root node is equal to the current node minus one except 2, we can direct the tail when we delete node assigned to the root node to keep the tree structural integrity, then downward adjustment, adjustment method starts with child node to node’s largest that comparison, then exchange value, The code is as follows:

var getLeastNumbers = function(arr, k) {
    if(k == 0) return [];
    // Reset the array that holds the minimum number of k
    data = [];
    // Resets the index from 0
    cnt = 0;
    // Iterate over the arR array and add data to data
    for(let i = 0; i < arr.length; i ++){
        // When k is stored in the data array, compare the current number with the root node of the big top heap. If it is large, do not add it; if it is small, add it first and then delete the root node
        if(data.length == k){
            if(arr[i] < data[0]){ push_up(arr[i]); pop_down(); }}else{ push_up(arr[i]); }}return data;
};
let data = [],cnt = 0;
var push_up = function(val){
    / / team
    data[cnt] = val;
    let idx = cnt;// The current node
    let rootIndex = Math.floor((idx - 1) /2);/ / the root node
    while(idx && data[idx] > data[rootIndex]){
        // If the newly added node is larger than the root node, the root node is changed and adjusted upward
        swpa(data[rootIndex],rootIndex,data[idx],idx);
        // Reset the current node
        idx = rootIndex;
        // Reset the root node
        rootIndex = Math.floor((idx - 1) /2);
    }
    cnt ++;
    return ;
}

var pop_down = function(){
    if(data.length <= 1) {
        data = [];
        return ;
    } 
    data[0] = data.pop();
    cnt --;
    let n = cnt - 1;// Sum up the number of points
    let idx = 0;// The current node
     let sonIndex = 2*idx + 1;// Left child node
     //sonIndex < n indicates that there is a left child node
    while( sonIndex <= n){
        let temp = idx;// Record the maximum index
        // The root node is compared with the left child node, whose index is assigned to temp
        if(data[idx] < data[sonIndex]) temp = sonIndex;
        // Determine whether the right child exists. If it exists, compare it with the current maximum value
        if( sonIndex + 1 <= n && data[temp] < data[sonIndex + 1] ) temp = sonIndex + 1;
        // If the current node is the maximum value, return the value without adjustment
        if(temp == idx) break;
        // The root node is not the largest
        swpa(data[temp],temp,data[idx],idx);
        // Reset the current node
        idx = temp;
        // Reset the left child of the current node
        sonIndex = 2*idx + 1;
    }
    return ;
}
// The two values are interchangeable
var swpa = function(v,i,v2,i2){
    data[i] = v2;
    data[i2] = v;
}
Copy the code