剑指offer40-最小的k个数

原题(来源Leetcode)

输入整数数组 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

解法

思想

堆或者基于快排的partition思想

代码

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        Queue<Integer> queue = new PriorityQueue<>();
        for(int i:arr) queue.offer(i);
        int[] ans = new int[k];
        for(int i = 0;i<k;i++) ans[i] = queue.poll();
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer40-%e6%9c%80%e5%b0%8f%e7%9a%84k%e4%b8%aa%e6%95%b0/

发表评论

电子邮件地址不会被公开。