解法一 随机切分
随机抽取数组中一个元素进行切分并返回该元素下标 index：
index == k-1
切分元素正好为第k个元素index < k-1
第k大的元素在下标为index元素的右边，对index右边的元素进行切分index > k-1
第k大的元素在下标为index元素的左边，对index左边的元素进行切分
class Solution {
Random rand = new Random();
public int[] getLeastNumbers(int[] arr, int k) {
if(arr == null || arr.length == 0 || arr.length < k || k <= 0)
return new int[]{};
int lo = 0;
int hi = arr.length - 1;
int index = partition(arr, lo, hi);
while(index != k - 1){
if(index > k - 1){
hi = index - 1;
index = partition(arr, lo, hi);
}else if(index < k - 1){
lo = index + 1;
index = partition(arr, lo, hi);
}
}
return Arrays.copyOfRange(arr, 0, k);
}
/**
* 随机切分函数
*/
private int partition(int[] a, int lo, int hi){
if(a == null || a.length == 0 || lo < 0 || hi > a.length)
throw new RuntimeException("Invalid Parameters");
int index = randRange(rand, lo, hi+1);
System.out.println(index);
exch(a, hi, index);
int small = lo - 1;
for(index = lo; index < hi; ++index){
if(a[index] < a[hi] ){
++small;
if(index != small){
exch(a, small, index);
}
}
}
small++;
exch(a, small, hi);
return small;
}
private int randRange(Random rand, int min, int max) {
if(max - min == 0) return min;
int r = rand.nextInt(max - min) + min;
return r;
}
private void exch(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
最大堆优先队列 适用于大量数据
使用一个容器添加k个数字。容器含有k个数字之后将新的数字与容器中的最大数字比较，如果新数大于最大值则新数不可能为最小的k个数之一，如果新数小于最大值则将容器的最大值提出，加入新数。
从容器中快速查询最大数可以使用最大优先队列，查询时间复杂度为O(1)，基于堆实现的的最大优先队列可以在O(logk)实现删除与插入操作。
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(arr == null || arr.length == 0 || arr.length < k || k <= 0)
return new int[]{};
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for(Integer each : arr){
if(maxPQ.size() < k){
maxPQ.add(each);
}else if(each < maxPQ.peek()){
maxPQ.poll();
maxPQ.offer(each);
}
}
int[] ans = new int[k];
for(int i = 0; i < k; i++){
ans[i] = maxPQ.poll();
}
return ans;
}
}