【剑指Offer】029——最小的k个数（链表）

题目描述

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

解题思路

两种方法：

• 法1：先对数组排序，然后取出前k个
• 法2：利用最大堆保存这k个数，每次只和堆顶比，如果比堆顶小，删除堆顶，新数入堆。

参考代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if(input == null || k == 0  || k > input.length) return res;
        Arrays.sort(input);
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
        
    }
    public ArrayList<Integer> GetLeastNumbers_Solution2(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if(input == null || k == 0  || k > input.length) return res;
        // PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。优先队列的作用是能保证每次取出的元素都是队列中权值最小的,通过比较器构造
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k,new Comparator<Integer){
            public int compare(Integer e1, Integer e2){
                return e2 -e1;
            }
        };
        for (int i = 0; i < input.length; i++) {
            if(maxHeap.size()!=k){
                maxHeap.offer(input[i]); // 添加数据
            }else{
                if(maxHeap.peek()>input[i]){
                    maxHeap.poll();  // 弹出数据
                    maxHeap.offer(input[i]);
                }
            }
        }
        for (Integer i : maxHeap) {
            res.add(i);
        }
        return res;
    }
}

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k == 0 or k > len(tinput): return []
        tinput = sorted(tinput)
        res = [tinput[i] for i in range(k)]
        return res

个人订阅号

image