剑指offer-题30：最小的k个数

我就是我 2022-05-28 07:47 154阅读 0赞

## **题目描述** ##

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

实验平台：[牛客网][Link 1]

--------------------

## **解决思路：** ##

![70][]  
![70 1][]

**注**：java中有一个数据结构是PriorityQueue，即优先队列。优先队列的元素默认按照其自然顺序进行排序，即默认为最小堆，若果需要实现最大堆，需要定义一个比较器，定义方式如下（其中k是优先队列的初始容量，若不定义，默认为11）：

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, (o1, o2) -> o2.compareTo(o1));

java:

import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.Iterator;
    import java.util.PriorityQueue;
    
    public class Solution {
        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> list = new ArrayList<Integer>();
    		if (input == null || input.length == 0 || k > input.length || k == 0) {
    			return list;
    		} else {
    			// 默认是通过自然顺序排序的最小堆，这里需要定义一个比较器来实现最大堆
    			PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, (o1, o2) -> o2.compareTo(o1));
    			for (int i = 0; i < input.length; i++) {
    				if (maxHeap.size() < k) {
    					maxHeap.offer(new Integer(input[i]));
    				} else if (maxHeap.peek() > input[i]) {
    					maxHeap.poll();
    					maxHeap.offer(input[i]);
    				}
    			}
    			Iterator<Integer> iterator = maxHeap.iterator();
    			while (iterator.hasNext()) {
    				list.add((Integer) iterator.next());
    			}
    			return list;
    		}
        }
    }

python:

略

[Link 1]: https://www.nowcoder.com/ta/coding-interviews?page=1
[70]: /images/20220528/2a727f2b712c4910b8efd1a3daa618a3.png
[70 1]: /images/20220528/cfc66b5210f34d6c809c3aff0817d040.png