[剑指offer] 最小的K个数

题目描述

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

解题思路

两种方法:

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

参考代码

法1:

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        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;
    }
}

法2:

import java.util.ArrayList;
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<Integer>();
        if(input == null || k ==0 || k > input.length)
            return res;
        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;
    }
}

版权属于: 尾尾部落

原文地址: https://weiweiblog.cn/getleastnumbers_solution/

转载时必须以链接形式注明原始出处及本声明。

window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"1","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM小冰成长之路

HDU-1512-Monkey King

ACM模版 描述 ? 题解 典型的左偏树! 问题的核心是当两个猴子帮派中的大佬斗争之后,这两个大佬要强壮值减半并且两个帮派进行合并。那么涉及到的操作有优先队列的...

2036
来自专栏数据结构与算法

多项式系数学习笔记

对于多项式$(x_1 + x_2 + x_3 + \dots + x_k) ^n$的展开式中$x_1^{d_1}x_2^{d_2}x_3^{d_3} \dots...

812
来自专栏算法与数据结构

数据结构 重点详解

线性数据结构 线性表-顺序表 代码实现: #include <bits/stdc++.h> #define TRUE 1 #define FALSE 0...

2806
来自专栏菩提树下的杨过

数据结构与算法C#版笔记--查找(Search)

做数据库开发的程序员,可能每天都会处理各种各样的查询sql,这个就是查找(Search)。通过查询记录主键字段(即主关键码)或其它非唯一字段(即次关键码)找到所...

2757
来自专栏小灰灰

线程安全的容器小结

线程安全的容器 列表 线程安全的列表有 Vector , CopyOnWriteArrayList 两种,区别则主要在实现方式上,对锁的优化上; 后者主要采...

2128
来自专栏尾尾部落

[剑指offer] 从上往下打印二叉树

就是二叉树的层序遍历。借助一个队列就可以实现。 使用两个队列一个存放节点,一个存放值。先将根节点加入到队列中,然后遍历队列中的元素,遍历过程中,访问该元素的左...

1091
来自专栏深度学习计算机视觉

java自定义构造二叉树及其遍历

首先:二叉树的建立 首先,我们采用广义表建立二叉树(关于广义表的概念,请查看百科的介绍:http://baike.baidu.com/view/203611.h...

3426
来自专栏jeremy的技术点滴

Java开发小技巧_02

4314
来自专栏来自地球男人的部落格

[LeetCode] 134. Gas Station

【原题】 There are N gas stations along a circular route, where the amount of gas...

2018
来自专栏计算机视觉与深度学习基础

Leetcode 171 Excel Sheet Column Number

Related to question Excel Sheet Column Title Given a column title as appear in...

21210

扫码关注云+社区

领取腾讯云代金券