題目：輸入n個整數(shù)嫌蚤，找出其中最小的K個數(shù)底哥。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字，則最小的4個數(shù)字是1,2,3,4,箫柳。
這個題能想到最簡單的方法就是利用排序算法對整個數(shù)組進(jìn)行排序讼育，然后取k個值帐姻。那么這個算法的復(fù)雜度就完全取決與排序算法的復(fù)雜度了粮宛。
image.png
上面是基于比較的排序算法的時間復(fù)雜度
- 但是仔細(xì)想一想，對整個數(shù)組進(jìn)行排序這個代價有點大卖宠，因為我們根本不需要后面n-k個數(shù)據(jù)有序巍杈。
- 所以應(yīng)該嘗試使用一個數(shù)組保存已經(jīng)掃過的所有的數(shù)中最大的k個數(shù)，在向后遍歷的過程中不斷更新這個數(shù)組扛伍， 這個復(fù)雜度大約就是O(n*k)了筷畦。
- k數(shù)組時用來保存幾個有序值的，那么我們可以利用大根堆來替換這個數(shù)組刺洒，這樣這個時間復(fù)雜度就可以優(yōu)化到O（n*logk了）
但是啊鳖宾。。逆航。這個題目對前面k個數(shù)也沒有任何順序要求鼎文，所以一定還有更完美的算法等著我們
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
if(input == null ||input.length < k || k == 0){
return new ArrayList<Integer>();
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
for(int i = 0; i < k; i++){
maxHeap.add(input[i]);
}
for(int i = k; i < input.length; i++){
if(maxHeap.peek() > input[i]){
maxHeap.poll();
maxHeap.add(input[i]);
}
}
return new ArrayList<Integer>(maxHeap);
}
}
