作者:whisper
链接:https://www.proprogrammar.com/article/909
声明:请尊重原作者的劳动,如需转载请注明出处
输入整数数组 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了,所以效率较高
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论