//小顶堆
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(arr == null || arr.length == 0 || k == 0) return new int[0];
PriorityQueue pq = new PriorityQueue<>((a, b) -> Integer.compare(a, b));
for(int num : arr){
pq.offer(num);
}
int[] result = new int[k];
for(int i = 0; i < k; i++){
result[i] = pq.poll();
}
return result;
}
}
//大顶堆
class Solution1 {
public int[] getLeastNumbers(int[] arr, int k) {
// 大顶堆，堆顶是最大元素
PriorityQueue pq = new PriorityQueue<>((a, b) -> {
return b - a;
});
for (int e : arr) {
// 每个元素都要过一遍二叉堆
pq.offer(e);
// 堆中元素多于 k 个时，删除堆顶元素
if (pq.size() > k) {
pq.poll();
}
}
// pq 中剩下的是 arr 中最小的 k 个元素
int[] res = new int[k];
int i = 0;
while (!pq.isEmpty()) {
res[i] = pq.poll();
i++;
}
return res;
}
}
//快排：关键在于找到第k小的数的位置
class Solution {
int[] res;
public int[] getLeastNumbers(int[] arr, int k) {
if(arr == null || arr.length == 0 || k == 0) return new int[0];
res = new int[k];
shuffle(arr);
int l = 0;
int r = arr.length - 1;
while(l <= r){
int idx = partition(arr, l, r);
if(idx < k - 1){
l = idx + 1;
}else if(idx > k - 1){
r = idx - 1;
}else{
for(int i = 0; i <= idx; i++){
res[i] = arr[i];
}
return res;
}
}
return res;
}
private int partition(int[] arr, int l, int r){
int i = l;
int j = r;
while(i < j){
while(i < j && arr[j] >= arr[l]) j--;
while(i < j && arr[i] <= arr[l]) i++;
swap(arr, i, j);
}
swap(arr, i, l);
return i;
}
//快排优化
private void shuffle(int[] nums){
Random rand = new Random();
int n = nums.length;
for (int i = 0 ; i < n; i++) {
// 生成 [i, n - 1] 的随机数
int r = i + rand.nextInt(n - i);
swap(nums, i, r);
}
}
private void swap(int[] arr, int idx1, int idx2){
int temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
}
public int[] getLeastNumbers(int[] arr, int k) {
// 输入：arr = [3,2,1], k = 2
//输出：[1,2] 或者 [2,1]
quickSort(arr, 0, arr.length-1);
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
public void quickSort(int[] arr, int left, int right) {
if (left > right)
return;
int jizhun = arr[left];
int i = left;
int j = right;
while (i < j) {
while (i<j&&arr[j]>=jizhun) j--;
while (i<j&&arr[i]<=jizhun) i++;
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
arr[left] = arr[i];
arr[i] = jizhun;
quickSort(arr, left, i-1);
quickSort(arr, i+1, right);
}
shuaidi
共以下 14 个回答
快排
c++ 代码 getLeastNumbers(vector & arr, int k) res;
class Solution {
public:
vector
{
vector
sort(arr.begin(),arr.end());
for(int i=0;i<k;i++)
res.push_back(arr[i]);
return res;
}
};
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
// 快排优化 哨兵 切割
//最小的k个数 哨兵下标=k-1 0 -k-1
qiege(arr,0,arr.length-1,k);
int result[] =new int[k];
for(int i=0;i<k;i++)
{
result[i]=arr[i];
}
return result;
}
快排思想：不用全部都排，只需要排好第k个小的数，那他之前的都会比他小，时间复杂度O（N）
堆：用大根堆来做，因为小根堆需要把元素都压入，而大根堆只需把更大的弹出，剩下的就都是前k小的数
8.1
Day23：下面是代码