剑指offer第六天

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;
}
}
上一篇:题解报告:hdu 1421 搬寝室(递推dp)


下一篇:Linux之指令 重定向 文件覆盖>和文件追加>>