1538-最小的k个数

最小的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

思路

最简单的思路就是进行排序,然后取前k个数返回即可.因为要求的结果并不要求有序,所以在排序过程中不要求完成全部排序,只需要确定前k个数即可.

代码

全部排序版本

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        fastSort(0,arr.length-1,arr);
        int[] result = new int[k];
        for(int i = 0;i < k;i++){
            result[i] = arr[i];
        }
        return result;
    }

    public void fastSort(int low,int high,int[] arr){
        if (low >= high){
            return;
        }
        int i = low;
        int j = high;
        int temp = arr[i];
        while(i < j){
            while(i < j && arr[j] >= temp){
                j--;
            }
            arr[i] = arr[j];
            while(i < j && arr[i] <= temp){
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = temp;
        fastSort(low,i-1,arr);
        fastSort(i+1,high,arr);
    }
}

部分排序版本

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        fastSort(0,arr.length-1,arr,k);
        int[] result = new int[k];
        for(int i = 0;i < k;i++){
            result[i] = arr[i];
        }
        return result;
    }

    public void fastSort(int low,int high,int[] arr,int k){
        if (high < k || low >= k){
            return;
        }
        int i = low;
        int j = high;
        int temp = arr[i];
        while(i < j && j >= k){
            while(i < j && arr[j] >= temp){
                j--;
            }
            arr[i] = arr[j];
            while(i < j && arr[i] <= temp){
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = temp;
        fastSort(low,i-1,arr,k);
        fastSort(i+1,high,arr,k);
    }
}

推荐阅读更多精彩内容

  • 前言 查找和排序算法是算法的入门常识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中...
    程序猿之路阅读 2,279评论 1赞 28
  • 排序算法说明 (1)排序的定义:对一序列对象根据某个关键字进行排序; 输入:n个数:a1,a2,a3,…,an 输...
    code武阅读 154评论 0赞 0
  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 1,109评论 0赞 1
  • Ba la la la ~ 读者朋友们,你们好啊,又到了冷锋时间,话不多说,发车! 1.冒泡排序(Bub...
    冷锋_007阅读 807评论 0赞 6
  • 参考:十大经典排序算法 0、排序算法说明 0.1排序的定义 对一序列对象根据某个关键字进行排序。 0.2 术语说明...
    谁在烽烟彼岸阅读 358评论 0赞 11