##題目描述 輸入n個整數，找出其中最小的K個數，例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4，
思路
大根堆存放最小的k個數，建堆復雜度為n，調整堆復雜度lgn，
時間復雜度O(nlgk)，空間復雜度O(k)，
代碼
import java.util.ArrayList;
import java.util.PriorityQueue;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
PriorityQueue<Integer> maxheap = new PriorityQueue<Integer>((x,y) -> y-x);
if(k > input.length || input == null || k == 0) return list;
for(int i = 0; i < k; i++) {
maxheap.offer(input[i]);
}
for(int i = k; i < input.length; i++) {
if(input[i] < maxheap.peek()) {
maxheap.remove();
maxheap.offer(input[i]);
}
}
for(Integer m : maxheap) {
list.add(m);
}
return list;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83464.html
標籤：其他
上一篇：軟體設計模式修煉 -- 原型模式
下一篇：連續子陣列的最大和