Topic describes

This is interview question 17.14 on LeetCode. Minimum K number, medium difficulty.

Tag: “priority queue”, “heap”, “sort”

Design an algorithm to find the smallest k number in an array. You can return these k numbers in any order.

Example:

Arr = [1,3,5,7,2,4,6,8], k = 4 output: [1,2,3,4]Copy the code

Tip:

  • 0 <= len(arr) <= 100000
  • 0 <= k <= min(100000, len(arr))

Priority queue (small root heap)

An intuitive idea is to use a “priority queue (small root heap)”, starting with all the elements in the heap, then taking KKK elements out of the heap and constructing the answers “sequentially”.

Code:

class Solution {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->a-b);
        for (int i : arr) q.add(i);
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = q.poll();
        returnans; }}Copy the code
  • Time complexity: The heap construction complexity is O(nlog⁡n)O(n\log{n})O(nlogn), and the solution construction complexity is O(klog⁡n)O(k\log{n})O(klogn). The overall complexity is O(nlog⁡n)O(n\log{n})O(nlogn)
  • Space complexity: O(n+k)O(n +k)O(n +k)

Priority queue (large root heap)

In solution one, we put all primitives into the heap, which has at most NNN elements, resulting in an upper bound on our complexity of O(nlog⁡n)O(n\log{n})O(nlogn).

Another good idea is to use a “priority queue” (large root heap).

When the original ARr [I]arr[I]arr[I] is processed, it is discussed according to the number of elements in the heap and its relationship with the elements on the top of the heap:

  • Arr [I]arr[I]arr[I]arr[I] into the heap;
  • The elements in the heap are
    k k     A: according to the
    a r r [ i ] arr[i]     Discussion on the relationship between the size of elements on the top of the heap:

    • > = heapToparr arr [I] [I] > = heapToparr [I] > = heapTop: Arr [I]arr[I]arr[I] can not belong to the KKK decimal (already KKK elements in the heap), directly discard arr[I]arr[I]arr[I];
    • Arr [I]

When the arrarrarr is processed, we use the heap elements to “reverse” the answer.

Code:

class Solution {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        int[] ans = new int[k];
        if (k == 0) return ans;
        for (int i : arr) {
            if (q.size() == k && q.peek() <= i) continue;
            if (q.size() == k) q.poll();
            q.add(i);
        }
        for (int i = k - 1; i >= 0; i--) ans[i] = q.poll();
        returnans; }}Copy the code
  • Time complexity: The heap construction complexity is O(nlog⁡k)O(n\log{k})O(nlogk), and the solution construction complexity is O(klog⁡k)O(k\log{k})O(klogk). The overall complexity is O(nlog⁡k)O(n\log{k})O(nlogk)
  • Space complexity: O(k)O(k)O(k)

All sorts

Arrays.sort in Java is implemented for comprehensive sorting. Different sorting implementations are selected based on the size of the data and whether the elements themselves are roughly ordered.

So a simpler implementation would be to sort using Arrays.sort and then construct the answers.

Code:

class Solution {
    public int[] smallestK(int[] arr, int k) {
        Arrays.sort(arr);
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) ans[i] = arr[i];
        returnans; }}Copy the code
  • Time complexity: Sort (assumedArrays.sortThe biaxis quicksort implementation is used
    O ( n log ⁡ n ) O(n\log{n})     ; Construct the answer complexity is
    O ( k ) O(k)     . The overall complexity is
    O ( n log ⁡ n ) O(n\log{n})
  • Space complexity: O(log⁡n+k)O(\log{n} +k)O(logn+k)

Fast array partitioning

Note that the question asks “return the KKK numbers in any order”, so we just need to make sure that the small numbers before KKK appear at [0,k)[0, k)[0,k).

This can be done using “quicksort” array partitioning.

We know that quicksort is always going to put values that are less than or equal to the base value on the left, and values that are greater than the base value on the right.

Therefore, we can determine whether the process is over by judging the relationship between the subscript IDXIDXIDX of the reference point and KKK:

  • Idx
  • Idx > kidX >kidx > K: base point left more than KKK, recursive processing left, so that the base point subscript left;
  • Idx =kidx =kidx =k: exactly KKK to the left of the datum, output elements to the left of the datum.

Code:

class Solution {
    int k;
    public int[] smallestK(int[] arr, int _k) {
        k = _k;
        int n = arr.length;
        int[] ans = new int[k];
        if (k == 0) return ans;
        qsort(arr, 0, n - 1);
        for (int i = 0; i < k; i++) ans[i] = arr[i];
        return ans;
    }
    void qsort(int[] arr, int l, int r) {
        if (l >= r) return ;
        int i = l, j = r;
        int ridx = new Random().nextInt(r - l + 1) + l;
        swap(arr, ridx, l);
        int x = arr[l];
        while (i < j) {
            while (i < j && arr[j] >= x) j--;
            while (i < j && arr[i] <= x) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        // Because the solution is described in terms of "to the left of the reference point" (not including the reference point), the use of k (k - 1 can also be dropped
        if (i > k) qsort(arr, l, i - 1);
        if (i < k) qsort(arr, i + 1, r);
    }
    void swap(int[] arr, int l, int r) {
        inttmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp; }}Copy the code
  • Time complexity: Since reference values are randomly selected each time, the average length of the array for each recursion is N /2n /2n /2, the number of array partitioning operations will not exceed 2∗n2 * n2∗n. The overall complexity is O(n)O(n)O(n)
  • Space complexity: O(log⁡n)O(\log{n})O(logn)

The last

This is the No. 17.14 interview question in our “Brush through LeetCode” series. The series began on January 21, 01/01, and there are 1916 questions in LeetCode by the start date.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.