题目描述

解法1：排序+取值

数组排序后取前k个值，注意特殊情况的判断，比如input数组长度比k还小

比如，那就返回整个数组即可。

import java.util.*;

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

Arrays.sort(input);使用的是快排。

时间复杂度：O(nlogn) 空间复杂度 O(k)

解法2：大根堆

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(input.length==0||k==0){
            return new ArrayList<Integer>();
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return o2 - o1;// 大根堆
            }
        });
        for(int i = 0; i<input.length; ++i){
            int tmp = input[i];
            if(pq.size()<k){
                pq.add(tmp);
            }else{
                if(tmp < pq.peek()){// pq不可能为空  不需要 !pq.isEmpty() 这个条件
                    pq.poll();
                    pq.add(tmp);
                }
            }
        }
        return new ArrayList<>(pq);
    }
}

时间复杂度：O(nlogk) 空间复杂度 O(k)

每次添加元素时，交换次数最大是 logk次。

题目扩展

前k个最大的数

只需要改两处即可

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(input.length==0||k==0){
            return new ArrayList<Integer>();
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();// 小根堆
        for(int i = 0; i<input.length; ++i){
            int tmp = input[i];
            if(pq.size()<k){
                pq.add(tmp);
            }else{
                if(tmp > pq.peek()){// pq不可能为空  不需要 !pq.isEmpty() 这个条件
                    pq.poll();
                    pq.add(tmp);
                }
            }
        }
        return new ArrayList<>(pq);
    }
}