本文共 1216 字，大约阅读时间需要 4 分钟。

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

import java.util.ArrayList;public class Solution {    public ArrayList
   
     GetLeastNumbers_Solution(int [] input, int k) {        ArrayList
    
      array = new ArrayList
     
      ();        if(input.length
      
       i;j--){                if(input[j]
      
     
    
   

标准答案：

import java.util.ArrayList;import java.util.PriorityQueue;import java.util.Comparator;public class Solution {   public ArrayList
   
     GetLeastNumbers_Solution(int[] input, int k) {       ArrayList
    
      result = new ArrayList
     
      ();       int length = input.length;       if(k > length || k == 0){           return result;       }        PriorityQueue
      
        maxHeap = new PriorityQueue
       
        (k, new Comparator
        
         () { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }); for (int i = 0; i < length; i++) { if (maxHeap.size() != k) { maxHeap.offer(input[i]); } else if (maxHeap.peek() > input[i]) { Integer temp = maxHeap.poll(); temp = null; maxHeap.offer(input[i]); } } for (Integer integer : maxHeap) { result.add(integer); } return result; }}
        
       
      
     
    
   

另外还有一种方法是基于快排寻找下标为k-1

转载地址：http://nyonn.baihongyu.com/