题目描述: 输入 n 个整数, 找出其中最小的 K 个数. 例如输入 4,5,1,6,2,7,3,8 这 8 个数字, 则最小的 4 个数字是 1,2,3,4,.
实现语言: Java
- import java.util.ArrayList;
- public class Solution {
- public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
- int size=input.length;
- ArrayList<Integer> res=new ArrayList<Integer>();
- if(size==0||input==null||size<k||k<=0){
- return res;
- }
- int start=0;
- int end=size-1;
- int index=partition(input,start,end);
- while(index!=k-1){
- if(index>k-1){
- end=index-1;
- index=partition(input,start,end);
- }else if(index<k-1){
- start=index+1;
- index=partition(input,start,end);
- }
- }
- for(int i=0;i<k;++i){
- res.add(input[i]);
- }
- return res;
- }
- private int partition(int[] input,int low,int high){
- int pivot=input[low];
- while(low<high){
- while(low<high&&input[high]>=pivot){
- --high;
- }
- input[low]=input[high];
- while(low<high&&input[low]<=pivot){
- ++low;
- }
- input[high]=input[low];
- }
- input[low]=pivot;
- return low;
- }
- }
实现语言: Java
- import java.util.ArrayList;
- import java.util.PriorityQueue;
- import java.util.Comparator;
- public class Solution {
- public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
- int size=input.length;
- ArrayList<Integer> res=new ArrayList<Integer>();
- if(size==0||input==null||size<k||k<=0){
- return res;
- }
- 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<size;++i){
- if(maxHeap.size()!=k){
- maxHeap.offer(input[i]);
- }else{
- if(maxHeap.peek()>input[i]){
- maxHeap.poll();
- maxHeap.offer(input[i]);
- }
- }
- }
- for(Integer num:maxHeap){
- res.add(num);
- }
- return res;
- }
- }
来源: http://www.bubuko.com/infodetail-2902008.html