通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

leetcode 剑指 Offer 40. 最小的k个数

268人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/909

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 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

难度:简单;标签:堆,分治算法;编程语言:JAVA


我的解法

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((i1, i2) -> i2 - i1);

        for(int i: arr){
            queue.offer(i);
            if(queue.size() > k){
                queue.poll();
            }
        }

        return queue.stream().mapToInt(i->i).toArray();
    }
}

又是一个堆的题,这里用大顶堆,将最大的数去除即可,保留最小的k个数


其它解法

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr.length == 0 || k == 0) {
            return new int[]{};
        }

        return quickSearch(arr, 0, arr.length - 1, k - 1);
    }

    private int[] quickSearch(int[] arr, int low, int high, int k) {
        int temp = partition(arr, low, high);
        if(temp == k) {
            return Arrays.copyOf(arr, k + 1);
        }

        return temp > k ? quickSearch(arr, low, temp - 1, k) : quickSearch(arr, temp + 1, high, k);
    }

    private int partition(int[] arr, int low, int high) {
        int mid = low + (high - low) / 2;
        if(arr[low] > arr[high]) swap(arr, low, high);
        if(arr[mid] > arr[high]) swap(arr, mid, high);
        if(arr[mid] > arr[low]) swap(arr, low, mid);
        int temp = low;
        int pivot = arr[low];

        while(low < high) {
            while(low < high && arr[high] >= pivot) high--;
            while(low < high && arr[low] <= pivot) low++;

            if(low < high) {
                swap(arr, low, high);
            }
        }
        swap(arr, low, temp);
        return low;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

这里用了快速排序,优点是不用全部排序,只要前k小的数排序了,就可以提前return了,所以效率较高


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告