【leetcode刷题】33.最小的k个数——Java版-阿里云开发者社区

【leetcode刷题】33.最小的k个数——Java版

2021-12-03 180

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： ⭐欢迎订阅《leetcode》专栏，每日一题，每天进步⭐先找到第k小的数，然后遍历一遍数组，把所有比k小的数加入结果集。然后用这个数填充结果集，使结果集大小等于k。——leetcode此题热评

前言

哈喽，大家好，我是一条。

糊涂算法，难得糊涂

今天给大家推荐一位字节算法大佬，ACM队长——「英雄哪里出来」

Question

剑指 Offer 40. 最小的k个数

难度：简单

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000

0 <= arr[i] <= 10000

Solution

该题是比较经典的TopK问题，解决的办法通常可以用快排、堆、二叉搜索树、计数排序。本文采用快速排序的方法，因为最高效。

快速排序：说白了就是给基准数据找其正确索引位置的过程.

根据快速排序原理，如果某次哨兵划分后基准数正好是第 k+1小的数字，那么此时基准数左边的所有数字便是题目所求的最小的 k 个数。

Code

所有leetcode代码已同步至github

欢迎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) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}