LeetCode 最小的k個(gè)數(shù) [簡單]
輸入整數(shù)數(shù)組 arr 偷办，找出其中最小的 k 個(gè)數(shù)囚企。例如挖炬，輸入4金吗、5拯欧、1箱季、6建芙、2旷偿、7、3降允、8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1艺糜、2剧董、3、4破停。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
示例 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
題目分析
解法1
使用大根堆實(shí)現(xiàn)
解法2
先把數(shù)組排序翅楼，然后取出前k個(gè)元素即可
代碼實(shí)現(xiàn)
public class GetLeastNumbers {
public static void main(String[] args) {
int[] arr = {3, 2, 1};
int k = 2;
int[] leastNumbers = getLeastNumbers(arr, k);
System.out.println(Arrays.toString(leastNumbers));
}
public static int[] getLeastNumbers1(int[] arr, int k) {
if (k == 0) {
return new int[0];
}
Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));
for (int ele : arr) {
if (heap.isEmpty() || heap.size() < k || ele < heap.peek()) {
heap.offer(ele);
}
if (heap.size() > k) {
heap.poll();
}
}
int[] res = new int[heap.size()];
int j = 0;
for (Integer ele : heap) {
res[j++] = ele;
}
return res;
}
public static int[] getLeastNumbers(int[] arr, int k) {
if (arr == null || arr.length == 0 || k == 0 || k > arr.length) {
return new int[]{};
}
if (k == arr.length) {
return arr;
}
int[] res = new int[k];
Arrays.sort(arr);
for (int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
}
