输入整数数组 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]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
堆
import java.util.Comparator;
import java.util.PriorityQueue;
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (arr == null || arr.length == 0 || k <= 0) {
return new int[0];
}
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return Integer.compare(o2, o1);
}
});
for (int x : arr) {
if (queue.size() == k) {
if (x < queue.peek()) {
queue.poll();
queue.offer(x);
}
} else {
queue.offer(x);
}
}
int[] ans = new int[k];
for (int i = ans.length - 1; i >= 0; --i) {
ans[i] = queue.poll();
}
return ans;
}
}
快速排序
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;
class Solution {
private void swap(int[] arr, int a, int b) {
int t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
private int[] partition(int[] arr, int L, int R) {
int privot = arr[L + (int) (Math.random() * (R - L + 1))];
int less = L - 1;
int more = R + 1;
int index = L;
while (index < more) {
if (arr[index] < privot) {
swap(arr, ++less, index++);
} else if (arr[index] == privot) {
index++;
} else {
swap(arr, index, --more);
}
}
return new int[]{less + 1, more - 1};
}
private int findKth(int[] arr, int k) {
int left = 0, right = arr.length - 1;
while (left < right) {
int[] partition = partition(arr, left, right);
if (k >= partition[0] && k <= partition[1]) {
return arr[k];
} else if (k < partition[0]) {
right = partition[0] - 1;
} else {
left = partition[1] + 1;
}
}
return arr[left];
}
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0) {
return new int[0];
}
int kth = findKth(arr, k - 1);
int[] ans = new int[k];
int index = 0;
for (int x : arr) {
if (x < kth) {
ans[index++] = x;
}
}
while (index < k) {
ans[index++] = kth;
}
return ans;
}
}