用刷題來練RUST Day16 Priority Queue Top K

17th鐵人賽

r_r_r_r_robert

2025-09-28 15:44:13

96 瀏覽

分享至

常用Priority Queue解的題型有

Top-K 問題
多來源候選

為何Top K 問題需要用Priority Queue

如果我們把整個陣列完整排序，然後取前 K 個，排序O(nlogn)、取前k個O(k)總共O(nlogn)，但是如果我們用一個min heap容量限制k個，把全部元素做完後O(nlogk)，當k遠小於n時，效能會比排序好得多，實際解一題來練習。

Leetcode 347. Top K Frequent Elements

題目：計算陣列中出現的數字，並回傳出現前k多的值有哪些，可以不用照順序排

輸入：nums = [1,1,1,2,2,3], k = 2

輸出：[1,2]

限制：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

解法：

如HashMap HashSet，這題如果用陣列暴力記出現頻率，時間雜度O(n^2)，計頻率用hashmap O(n)或是這題因為給的條件是-10^4 <= nums[i] <= 10^4也可以開2*10^4+1陣列去記，把num[i]的頻率記到num[i]+10^4，時間複雜度也是O(n)
知道全部數字出現頻率後可以用排序法時間複雜度O(nlogn)或是priority queue O(nlogk)

use std::collections::{HashMap,BinaryHeap};
use std::cmp::Reverse;
impl Solution {
    pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut map = HashMap::new();
        let mut ans = Vec::new();
        let mut heap:BinaryHeap<(Reverse<i32>,i32)> =BinaryHeap::new();
        
        for element in nums {
            map.entry(element).and_modify(|count| *count=*count+1).or_insert(1);
        }

        for(&key,&value) in map.iter() {
            if(k as usize>heap.len()){
                heap.push((Reverse(value),key));
            } else if let Some(& (Reverse(top),_))=heap.peek(){
                if top<value{
                    heap.pop();
                    heap.push((Reverse(value),key));
                }
            }
        }

        for &(_, v) in heap.iter(){
           ans.push(v);
        }
        ans
    }
}

如何比較多個順序

前面範例只有比較一個值，如何比較多個值？

在Rust中heap存的值如果是tuple(A,B,..)，會依序比較A字典序，如果A相同在比較B……以此類推。

資料來源：https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html

參考資料：https://doc.rust-lang.org/std/primitive.tuple.html#:~:text=The%20sequential%20nature,non%2Dequal%20set%20is%20found

資料來源：https://doc.rust-lang.org/std/cmp/trait.Ord.html#lexicographical-comparison

我們直接刷一題來看

leetcode 692. Top K Frequent Words

題目：給一個向量陣咧存字串，統計字串出現次數，一出現頻率多到少回傳前k個最常出現字串，如果頻率一樣比較字串順序

輸入：words = ["i","love","leetcode","i","love","coding"], k = 2

輸出：["i","love"]

限制：

1 <= words.length <= 500
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
k is in the range [1, The number of unique words[i]]

解法：如Leetcode 347. Top K Frequent Elements先用hashmap統計次數，再用miniheap記錄前k筆大小，因為heap中存(頻率，字串)tuple，所以當頻率相同會判斷字串順序

use std::collections::{HashMap,BinaryHeap};
use std::cmp::Reverse;

impl Solution {
    pub fn top_k_frequent(words: Vec<String>, k: i32) -> Vec<String> {
        let mut map =HashMap::new();
        for string in words{
            map.entry(string).and_modify(|count| *count=*count+1).or_insert(1);
        }
        let mut heap:BinaryHeap<(Reverse<i32>,String)> = BinaryHeap::new();

        for (key,value) in map.into_iter() {
            if(k as usize>heap.len()){
                heap.push((Reverse(value),key));
            } else if let Some(top) = heap.peek() {
                let insert_key = (Reverse(value),key);
                if(*top>insert_key){
                    heap.push(insert_key);
                    heap.pop();
                }
            }
            
        }
        let mut ans =Vec::new();
        for i in 0..heap.len(){
            ans.push(heap.pop().unwrap().1);
        }
        ans.reverse();
        ans
    }
}