每天一道劍指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;      }  }

程式碼截圖（避免亂碼）