最小的k个数 - Java

题目描述

给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组

示例1

输入

[4,5,1,6,2,7,3,8],4 
           

返回值

[1,2,3,4]
           

方法一（排序后，再取前k个值）

这个没什么好讲的，肯定不是最优解。

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result=new ArrayList<>();
        if(input.length>=k&&k>0){
            Arrays.sort(input);
            for(int i=0;i<k;i++){
                result.add(new Integer(input[i]));
            }
 
        }
        return result;
 
    }
}
           

方法二（堆排序）

使用大顶堆，大顶堆的peek()最大（即最大值在最顶部）。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> ret = new ArrayList<>();
        if(k==0 || k>input.length){
            return ret;
        }
        Queue<Integer> minheap =new PriorityQueue<Integer>(11, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for(int value: input){
            if(minheap.size() < k){
                minheap.offer(value);
            }else{
                System.out.println(minheap.peek());
                if(value < minheap.peek()){
                    minheap.poll();
                    minheap.add(value);
                }
            }
        }
        while(!minheap.isEmpty()){
            ret.add(minheap.peek());
            minheap.poll();
        }
        return ret;
    }
}