侧边栏壁纸
博主头像
秦怀杂货店博主等级

纵然缓慢,驰而不息。

  • 累计撰写 141 篇文章
  • 累计创建 37 个标签
  • 累计收到 11 条评论
隐藏侧边栏

剑指Offer【29】-- 最小的k个数

秦怀杂货店
2020-12-26 / 0 评论 / 0 点赞 / 205 阅读 / 0 字
温馨提示:
本文最后更新于 2020-12-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

[toc]

题目描述

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

思路与解析

下面方法的思路比较简单,但是比较取巧,直接借助了大顶堆,也就是上面的元素是最大的。如果里面个数超过k的话,则弹出堆顶的元素。
这里不展开最大堆和最小堆的具体讲解,什么是最大堆/最小堆呢?

  • 大/小堆树是完全二叉树
  • 大/小堆树的每一个节点不小于/不大于其孩子节点。

这道题我们用的是最大堆,也就是最上面的元素是最大的,如果个数超过k的话,那么就把堆顶的元素弹出去,也就是优先将最大的弹出。

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        if (input == null || k > input.length || k <= 0) {
            return new ArrayList<>();
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int num : input) {
            priorityQueue.add(num);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }
        return new ArrayList<>(priorityQueue);
    }
}

此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~

技术之路不在一时,山高水长,纵使缓慢,驰而不息。

公众号:秦怀杂货店

0

评论区