Offer 40. Minimum number of k

“This is my 37th day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

Force button topic link

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

Limitations:

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

Ideas:

First consider using brute force to solve the problem. The idea is to sort the array, take the first K and return it.

Violence law

/ * * *@param {number[]} arr
 * @param {number} k
 * @return {number[]}* /
const getLeastNumbers = (arr, k) = > {
    return arr.concat().sort((a, b) = > a - b).slice(0, k)
};
Copy the code

Analysis:

The brute force method is purely an ARRAY API. It is not recommended to use this method in interviews. Just as an idea.

Fast row

In the above method, we directly use the sort method provided by arrays. Here we use quicksort for sorting.

According to the requirements of the problem, only need to divide the array into the smallest k number and other two parts, and quicksort sentinel partition can accomplish this goal.

So the idea is that after we partition the sentries, we can tell if the sentries are equal to k in the index of the array. Because the index is equal to k, that means all the numbers to the left of the sentinel are smaller than the sentinel, which is the smallest number of k.

Here’s the code:

/ * * *@param {number[]} arr
 * @param {number} k
 * @return {number[]}* /
const quickSort = (arr, k, l, r) = > {
    if (l >= r) return;
    let i = l;
    let j = r;
    while(i < j) {
        while(i < j && arr[j] >= arr[l]) j--;
        while(i < j && arr[i] <= arr[l]) i++;
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }
    [arr[l], arr[i]] = [arr[i], arr[l]];
    if (i > k) quickSort(arr, k, l, i - 1);
    if (i < k) quickSort(arr, k, i + 1, r);
    return arr.slice(0, k);
}

const getLeastNumbers = (arr, k) = > {
    if (k >= arr.length) return arr; If k is greater than or equal to the target array length, return the array
    return quickSort(arr, k, 0, arr.length - 1); // Start quick sorting
};
Copy the code

Time complexity O(N).
Space complexity O(logN).

Analysis:

Let’s start with the logic inside the main function. If k is greater than or equal to the length of the array, that means the smallest number of k is the array itself, so you just return the array.

Then enter the logic of the quick sorting function. Different from ordinary quick sorting, an additional parameter K is needed to judge the relationship between the position of the sentry and K in the process of quick sorting.

Next is the logic of the quick arrangement, here will not do the analysis, specific can look at the problem solution. Fast forward to the next step in the switch sentry position. After swapping the sentinels, the array is divided into two parts by the sentinels. The value of the first half is less than the sentinels, and the value of the second half is greater than the sentinels.

At this point, the relationship between the sentry position and K needs to be determined. If the sentry position is greater than k, it means that the first k minimum numbers are in the left subarray. At this point, we need to continue to recursively fast-sort the left subarray. If the sentry position is less than k, it means that part of the first k smallest numbers are in the right subarray. In this case, we need to continue to recursively fast-sort the right subarray. If the sentinel position is equal to k, that means the array to the left of the sentinel is the first k minima. The first k values of the returned array are simply intercepted.

conclusion

A. sort b. sort C. sort D. sort We can either use the sorting algorithm provided by arrays or implement our own sorting algorithm. A fast sorting algorithm is used to find the final solution. Because the sentry division in the quickplatoon fits the problem very well and can be used reasonably.

In terms of complexity, the time complexity of sentry division for an array with length N is O(N). The average recursion depth of partition functions is order log N.

Offer 40. Minimum number of k