Nuggets team number online, help you Offer impromptu! Click for details

Topic describes

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

Their thinking

There are two ways to solve this problem:

Solution a:

  1. Sort the array, the array sort method has many, this article uses the quick sort;
  2. Using js splice or slice, the first k bytes of the array are returned

Solution 2: If you have learned data structure heap, you can use heap to sort, need to maintain a small root heap (usually refers to the smallest heap. Minimum heap is a sorted binary tree in which the data value of any non-terminal node is no greater than the value of its left and right children), and the first k elements in the sorted heap are the results to be returned.

The problem solving code

Solution one code:

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let centerIndex = Math.floor(arr.length / 2);
    let centerValue = arr.splice(centerIndex, 1) [0];
    let left = [], right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < centerValue) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([centerValue], quickSort(right))
}
var getLeastNumbers = function (arr, k) {
    const minList = quickSort(arr);
    return minList.slice(0, k);
};
Copy the code

Solution two code:

function buildHeap(arr) {
    let len = arr.length;
    for (let i = Math.floor(len / 2); i >= 0; i--) { heapAdjust(arr, i, len); }}// Swap variables
function swap(arr, i, child) {
    if (i === child) return;
    arr[i] = arr[child] + arr[i];
    arr[child] = arr[i] - arr[child];
    arr[i] = arr[i] - arr[child];
}
var getLeastNumbers = function (arr, k) {
    let len = arr.length;
    let res = [];
    if (k === 0) return [];
    if (k === len) return arr;
    buildHeap(arr);
    for (let i = 1; i <= k; i++) {
        res.push(arr[0]);
        swap(arr, 0, len - i);
        heapAdjust(arr, 0, len - i);
    }
    return res;
};
function heapAdjust(arr, i, len) {
    let child = i * 2 + 1;
    while (child < len) {
        if (child + 1 < len && arr[child] > arr[child + 1]) {
            child = child + 1;
        }
        if (arr[child] < arr[i]) {
            swap(arr, i, child);
            i = child;
            child = i * 2 + 1;
        } else {
            break; }}}Copy the code

conclusion

Although solution 2 has more code, it reflects a way of thinking and uses data structure to solve the problem.