題目描述

輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4,。

?

?

題目解答

使用小根堆
將n個元素全放進小根堆，再一個一個的彈出來，彈前k個為最小的K個
時間復雜度為O(N)+Klog（N）；

import java.util.ArrayList; import java.util.PriorityQueue;public class GetLeastNumbersMe {public static void main(String[] args) {int[] arr = {4,5,1,6,2,7,3,8};GetLeastNumbersMe me = new GetLeastNumbersMe();ArrayList<Integer> list = me.GetLeastNumbers_Solution(arr,5);System.out.println(list.toString());}public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {ArrayList<Integer>list=new ArrayList<>();if(k>input.length||k==0)return list;PriorityQueue<Integer> minStack=new PriorityQueue<>();for(int i=0,len=input.length;i<len;i++){minStack.add(input[i]);}for(int i=0;i<k;i++){list.add(minStack.poll());}return list;}}

?

總結

以上是生活随笔為你收集整理的常考数据结构与算法:最小的k个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。