Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Like it and see. Make it a habit. Wechat search [a coding] follow this programmer who is struggling in the Internet.

This article is collected on Github – Technical expert Training, which contains my learning route, series of articles, interview question bank, self-study materials, e-books, etc.

Find the KTH smallest number, and then iterate through the array, adding all numbers less than k to the result set. Then fill the result set with this number, making the result set size equal to k.

— Leetcode

preface

Hello, everyone. I’m One.

Confused algorithm, rarely confused

Today I would like to recommend a byte algorithm guru, Captain ACM — “Where the heroes come from”

Question

Offer 40. Minimum number of k

Difficulty: Easy

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

Solution

This problem is a classic TopK problem, the solution can usually use fast sorting, heap, binary search tree, counting sort. This paper adopts the method of quick sort, because it is the most efficient.

Quicksort: Basically, the process of finding the correct index position for the base data.

According to the principle of quicksort, if the base number of a sentinel partition happens to be the k+1 smallest number, then all the numbers to the left of the base number are the smallest number of k.

Code

All LeetCode codes have been synchronized to Github

Welcome to star

/ * * *@author yitiaoIT
 */
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length) return arr;
        return quickSort(arr, k, 0, arr.length - 1);
    }
    private int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        return Arrays.copyOf(arr, k);
    }
    private void swap(int[] arr, int i, int j) {
        inttmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }}Copy the code

Result

Complexity analysis

  • Time complexity: O(N)

Last

One foot is difficult to go, one hand is difficult to sing, a person’s power is limited after all, a person’s journey is doomed to be lonely. When you set a good plan, with full of blood ready to set out, must find a partner, and Tang’s monk to the West, the master and his disciples four people united as one to pass the ninety-eight difficult. So,

If you want to get into a big factory,

To learn data structures and algorithms,

If you want to keep brushing,

To have a group of like-minded people,

Please join the team to brush the questions