29.最小的K个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
解法一：
Partition思想
允许改变原始数组的情况，时间复杂度O(n)，不适合海量数据
import java.util.ArrayList;
public class Solution {
/*解法一：允许改变原始数组的情况，时间复杂度O(n)，不适合海量数据*/
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
//注意如果输入不合法，这里返回的是一个空集合，不是Null，与return null不同
if(input == null || k<0 || k>input.length) return result; int start = 0;
int end = input.length-1;
int smallNums = partition(input,start,end);
while(smallNums != k-1){
if(smallNums > k-1)
smallNums = partition(input,start,smallNums-1);
else if(smallNums < k-1)
smallNums = partition(input,smallNums+1,end);
}
for(int i =0;i<k;i++){
result.add(input[i]);
}
return result;
}
//快排方法功能函数，在指定范围内随机选取一个数字，将数组中大与等于的放置其又，小于的放置其左；
//返回值是在变换位置后，该元素的索引值
public static int partition(int[] array,int start,int end){
//边界检测
if(array == null || array.length == 0 || start < 0 || end >= array.length || start > end) return -1;
//在[start,end]范围内，随机选取一个数作为index
int randomIdx = (int)(start + Math.random()*(end-start));
//int length = array.length;
int smallNums = start-1;
swap(array,randomIdx,end);
for(int i=start;i<end;i++){
if(array[i] < array[end]){
smallNums++;
if(smallNums < i){
swap(array,smallNums,i);
}
}
} smallNums++;
swap(array,smallNums,end);
return smallNums;
}
//交换元素
public static void swap(int[] array,int i,int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
解法二：
使用最大堆思想，通过优先队列的Conparator定制排序，实现指定大小的最大堆。
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
//解法二：不改变原始数组，使用优先队列，时间复杂度O(nlogk)，适合海量数据
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if(input == null || k > input.length || k<=0) return result;
PriorityQueue<Integer> maxQueue = new PriorityQueue(k,new Comparator<Integer>(){
@Override
public int compare(Integer o1,Integer o2){
return o2.compareTo(o1);//将先前Integer中的自然排序（从小到大）反过来，实现从大到小；
}
});
for(int i =0;i<input.length;i++){
if(maxQueue.size() != k ){
maxQueue.offer(input[i]);
}else if(maxQueue.peek() > input[i]){
Integer temp = maxQueue.poll();//必须先去除队列头部的数据,以保证队列长度
temp = null;
maxQueue.offer(input[i]);
}
}
for(Integer i : maxQueue){
result.add(i);
}
return result;
}
}