常用Priority Queue解的題型有
Top-K 問題
多來源候選
如果我們把整個陣列完整排序,然後取前 K 個,排序O(nlogn)、取前k個O(k)總共O(nlogn),但是如果我們用一個min heap容量限制k個,把全部元素做完後O(nlogk),當k遠小於n時,效能會比排序好得多,實際解一題來練習。
題目:計算陣列中出現的數字,並回傳出現前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/cmp/trait.Ord.html#lexicographical-comparison
我們直接刷一題來看
題目:給一個向量陣咧存字串,統計字串出現次數,一出現頻率多到少回傳前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
}
}