每天一道剑指offer-最小的K个数

乔戈里

发布于 2019-09-17 16:06:43

2950

发布于 2019-09-17 16:06:43

文章被收录于专栏：Java那些事Java那些事

前言

今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

昨天的题解

题目

每天一道剑指offer-最小的K个数来源： https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目详述

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

题目详解

思路

使用一个大小为K的最大堆，然后堆里面最大的数是堆顶，然后每次比较堆顶的数和数组中的数，如果堆顶的数比数组中的数A大，那么就把堆顶的数弹出来，把数组中的数A进堆，这样子到最后堆里面的堆顶始终是比外面的数小，而堆里的其他数是小于堆顶的数（最大堆的性质），所以堆中的数就是最小的k个数

代码

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> resultList = new ArrayList<>();
        if(k > input.length || k<=0)
            return resultList;
        //使用优先级队列建堆，优先级队列默认是最小堆，所以要重写比较器
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer o1,Integer o2){
                return o2.compareTo(o1);
            }
        }
        );
        for(int i=0;i<input.length;i++)
        {
            if(i < k){//如果没有达到k个数，那么直接入堆
                maxHeap.add(input[i]);
            }else{
                if(maxHeap.peek() > input[i])
                {//堆顶的数比数组当前的数大，那么就堆顶出堆
                    maxHeap.poll();
                    maxHeap.add(input[i]);//把当前数加入堆中
                }
            }
        }
        while(maxHeap.isEmpty() != true)
            resultList.add(maxHeap.poll());//把堆中的数出堆添加到结果数组中
        return resultList;
    }
}