iT邦幫忙

2025 iThome 鐵人賽

DAY 16
0
Rust

用刷題來練RUST系列 第 16

用刷題來練RUST Day16 Priority Queue Top K

  • 分享至 

  • xImage
  •  

常用Priority Queue解的題型有

  1. Top-K 問題

  2. 多來源候選

為何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.

解法:

  1. 如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)

  2. 知道全部數字出現頻率後可以用排序法時間複雜度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://ithelp.ithome.com.tw/upload/images/20250928/20142205ffLWIj9GuQ.png
資料來源:https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html

https://ithelp.ithome.com.tw/upload/images/20250928/2014220571xhKq9jcw.png
參考資料:https://doc.rust-lang.org/std/primitive.tuple.html#:~:text=The%20sequential%20nature,non%2Dequal%20set%20is%20found

https://ithelp.ithome.com.tw/upload/images/20250928/20142205NBLugP6Iw0.png
資料來源: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
    }
}

Day16總結

  1. BinaryHeap只有一個值要比較,比較該值的字典順序。
  2. 如果比較的是tuple,從頭開始比較字典順序直到出現不同值。
  3. Top K問題用min heap解,當heap滿了,比較插入的值要大於peek在插入,O(nlogk)

參考資料

  1. https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html
  2. https://doc.rust-lang.org/std/primitive.tuple.html#:~:text=The%20sequential%20nature,non%2Dequal%20set%20is%20found
  3. https://doc.rust-lang.org/std/cmp/trait.Ord.html#lexicographical-comparison

上一篇
用刷題來練RUST Day15 優先佇列 Priority Queue
下一篇
用刷題來練RUST Day17 如何自訂義Priority Queue Top K比較方式
系列文
用刷題來練RUST19
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言