查找 TopK 問題

​從海量數字中尋找最大/小的 k 個，這類問題我們稱為 TopK 問題。

通常使用資料結構-最大/小堆來解決

• 求前 k 大，用最小堆，即堆頂元素為堆中最小值。
• 求前 k 小，用最大堆，即堆頂元素為堆中最大值。

如前k大的值, 傳入清單 list=[12, 39, 3, 72, 56, 81, 15, 9, 103] 和 k=3, 輸出 [103, 81, 72]。

如前k小的值, 傳入清單 list=[12, 39, 3, 72, 56, 81, 15, 9, 103] 和 k=3, 輸出 [3, 9, 12]。

前K大值

思路：

疊代清單元素：

• 1.先放入元素前 k 個建立一個最小堆；
• 2.目前元素x若大于堆頂元素：移除堆頂元素并入隊x；
• 3.最後擷取 最小堆 中的值，即為 topK4Max。

JAVA參考代碼

public static int[] topK4Max(int[] nums, int k) {
​
    // 優先隊列、從小到大 (預設也是自然排序)
    Queue<Integer> minHeap = new PriorityQueue<>(Comparator.naturalOrder());
    // 建立最小堆
    for (int i = 0, len = nums.length; i < len; i++) {
        if (minHeap.size() < k) {
            minHeap.offer(nums[i]); // 入隊
            continue;
        }
        if (nums[i] > minHeap.peek()) { // 取隊首元素比較，不移除
            minHeap.poll(); // 取隊首元素，并移除
            minHeap.offer(nums[i]);
        }
    }
    // 周遊隊列
    List<Integer> list = new ArrayList<>();
    Iterator<Integer> iterator = minHeap.iterator();
    while (iterator.hasNext()){
        list.add(iterator.next());
    }
    // 從大到小排序
    Collections.sort(list, (o1, o2) -> o1 < o2 ? 1 : o1 == o2 ? 0 : -1);
    // 轉換成數組
    return list.stream().mapToInt(Integer::valueOf).toArray();
​
}
           

前K小值

思路：

疊代清單元素：

• 1.先放入元素前 k 個建立一個最大堆；
• 2.目前元素x若小于堆頂元素：移除堆頂元素并入隊x；
• 3.最後擷取 最大堆 中的值，即為 topK4Min。

JAVA參考代碼

public static int[] topK4Min(int[] nums, int k) {
​
    // 優先隊列、從大到小排序
    Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    // 建立最大堆
    for (int i = 0, len = nums.length; i < len; i++) {
        if (maxHeap.size() < k) {
            maxHeap.offer(nums[i]); // 入隊
            continue;
        }
        if (nums[i] < maxHeap.peek()) { // 取隊首元素比較，不移除
            maxHeap.poll(); // 取隊首元素，并移除
            maxHeap.offer(nums[i]);
        }
    }
    // 周遊隊列
    List<Integer> list = new ArrayList<>();
    Iterator<Integer> iterator = maxHeap.iterator();
    while (iterator.hasNext()){
        list.add(iterator.next());
    }
    // 從小到大排序
    Collections.sort(list);
    // 轉換成數組
    return list.stream().mapToInt(Integer::valueOf).toArray();
    
}
           

測試代碼

public static void main(String[] args) {
    int[] nums = new int[]{12, 39, 3, 72, 56, 81, 15, 9, 103};
​
    int[] maxK = topK4Max(nums, 3);
    System.out.println(JSON.toJSONString(maxK));
​
    int[] minK = topK4Min(nums, 3);
    System.out.println(JSON.toJSONString(minK));
}
           

更多文章歡迎掃碼關注公衆号 [JAVA覓音閣] 檢視