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

• 2019 年 10 月 4 日
• 筆記

前言

今天的题目 每天的题目见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;      }  }

代码截图（避免乱码）