锐客网

  1. 首页 > it技术 > >

leetcode|剑指Offer-40-最小的k个数--topk问题java解法整理

java算法leetcode排序算法

leetcode|剑指Offer-40-最小的k个数--topk问题java解法整理
文章图片

解法来自于：小美算法 剑指Offer 40题 最小的k个数 java版本 层层深入的三种解法来赢得面试
解法一：排序+取前k个数

class Solution { public int[] getLeastNumbers(int[] arr, int k) { int[] res=new int[k]; //排序 Arrays.sort(arr); for(int i=0; i

解法二：优先队列大顶堆解法
class Solution { //利用小顶堆 大根堆的做法 public int[] getLeastNumbers(int[] arr, int k) { //创建一个队列(默认是最大堆(默认每次被踢出的都是最小的),，我们需要把它改成最小堆（每次被提出的都是最大的）) Queue queue=new PriorityQueue<>((o1,o2)->(o2.compareTo(o1))); for(int i:arr){ queue.add(i); //保证队列里只装k个数，且不断保留最小的k个 while(!queue.isEmpty()&& queue.size()>k) queue.poll(); } //创建新的数组，返回结果 int[] res=new int[k]; for(int i=0; i

解法三：快排+二分
class Solution { //快排+二分 public int[] getLeastNumbers(int[] arr, int k) { //排除空数组情况 if(arr==null||arr.length==0) return new int[0]; //记录数组两端，不断缩小范围 int lo=0,hi=arr.length-1; //使用二分法，不断筛选范围 while(lo

【leetcode|剑指Offer-40-最小的k个数--topk问题java解法整理】解法三图示理解：
leetcode|剑指Offer-40-最小的k个数--topk问题java解法整理
文章图片

    推荐阅读


    上一篇：dataframe两个表合并|dataframe两个表合并_Pandas数据变换-长宽表互换

    下一篇：深入浅出|五分钟带你速通Spring IOC