劍指offer JZ29 最小的K個數

題目連結：

JZ29 最小的K個數

給定一個數組，找出其中最小的K個數。例如數組元素是4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4。如果k > 數組的長度，那麼傳回一個空的數組。

本題思路：

大根堆 實時維護數組的前 k 小值。

首先将前 k 個數插入大根堆中，随後從第 k+1個數開始周遊，如果目前周遊到的數比大根堆的堆頂的數要小，就把堆頂的數彈出，再插入目前周遊到的數。最後将大根堆裡的數存傳入連結表傳回即可。

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        if(k == 0 || input.length == 0) return new ArrayList<>(); // 避免空指針異常
        
        // PriorityQueue預設小根堆 大根堆需要重寫比較器
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 - o1); // queue裡元素按從大到小排列
        
        for(int num : input) {
            if(queue.size() < k) { // 将前 k 個數插入大根堆中
                queue.offer(num);
            } else if(queue.peek() > num) {
                queue.poll();
                queue.offer(num); // 放入後自動排序 最大值依舊在隊首等待queue.poll();
            }
        }
        
        ArrayList<Integer> list = new ArrayList<>();
        if(k > input.length) return list; // 如果k > 數組的長度 那麼傳回一個空的連結清單
        for(int num : queue) {
            list.add(num);
        }
        return list;
    }
}
           

相似題目

leetcode 215. 數組中的第K個最大元素

在未排序的數組中找到第 k 個最大的元素。請注意，你需要找的是數組排序後的第 k 個最大的元素，而不是第 k 個不同的元素。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(k == 0 || nums.length == 0) return 0;

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int num : nums) {
            if(queue.size() < k) {
                queue.offer(num);
            } else if(queue.peek() < num) { // 大的留在queue裡
                queue.poll();
                queue.offer(num);
            }
        }
        // queue裡是最大的k個數 按從小到大排列
        // 從隊尾數到隊頭 隊頭恰好是第 k 大
        int res = queue.poll(); 
        return res;
    }
}