สมมติว่าเรามีรายการคำที่ไม่ว่างเปล่า เราต้องหาองค์ประกอบ k ที่พบบ่อยที่สุด คำตอบของเราควรจัดเรียงตามความถี่จากสูงสุดไปต่ำสุด เมื่อคำสองคำมีความถี่เท่ากัน คำที่เรียงตามตัวอักษรต่ำกว่าจะถูกวางไว้ในตอนแรก ดังนั้นหากอาร์เรย์เป็นเหมือน ['the', 'sky', 'is', 'blue', 'the', 'weather', 'is', 'comfortable'] คำที่ใช้บ่อยที่สุดคือ ["คือ" "the","สีน้ำเงิน"]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดหนึ่งแผนที่เรียกว่า m
- สร้างลำดับความสำคัญหนึ่งคิว v
- สำหรับ i :=0 ถึง n โดยที่ n คือขนาดของอาร์เรย์คำ จากนั้นเพิ่ม m[words[i]] ขึ้น 1
- สำหรับแต่ละองค์ประกอบ e ในแผนที่
- ถ้าขนาดของ v
- มิฉะนั้น หากค่าของ v.top คือ <ค่าของ e ให้ลบองค์ประกอบด้านบนออกจาก v แล้วแทรก e ลงใน v.
- มิฉะนั้น ถ้าค่าของ v.top คือ =ค่าของ e และคีย์ของ v.top คือ> คีย์ของ e จากนั้นให้ลบองค์ประกอบด้านบนออกจาก v แทรก e ลงใน v
- ถ้าขนาดของ v
- กำหนดหนึ่งอาร์เรย์ที่เรียกว่า res
- ในขณะที่ v ไม่ว่างเปล่า
- อุณหภูมิ :=ด้านบนของ v
- ลบด้านบนออกจาก v
- ใส่คีย์ของ temp ลงในอาร์เรย์ res
- ย้อนกลับอาร์เรย์ res
- ผลตอบแทน
ตัวอย่าง(C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
struct Comparator{
bool operator()(pair <string ,int> a, pair <string, int> b){
if(a.second != b.second) return !(a.second < b.second);
return !(a.first > b.first);
}
};
class Solution {
public:
static bool cmp(pair <string, int> a, pair <string, int> b){
if(a.second != b.second) return a.second > b.second;;
return a.first < b.first;
}
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> m;
priority_queue < pair <string, int>, vector < pair <string, int> >, Comparator > v;
for(int i = 0; i < words.size(); i++){
m[words[i]]++;
}
map<string, int> :: iterator i = m.begin();
while(i != m.end()){
if(v.size() < k){
v.push(*i);
}
else if(v.top().second < i->second){
v.pop();
v.push(*i);
}
else if(v.top().second == i->second && v.top().first > i->first){
v.pop();
v.push(*i);
}
i++;
}
vector <string> res;
while(!v.empty()){
pair <string, int> temp = v.top();
v.pop();
res.push_back(temp.first);
}
reverse(res.begin(), res.end());
return res;
}
};
main(){
Solution ob;
vector<string> v = {"the", "sky", "is", "blue", "the", "weather", "is", "comfortable"};
print_vector(ob.topKFrequent(v, 3));
} อินพุต
["the", "sky", "is", "blue", "the", "weather", "is", "comfortable"] 3
ผลลัพธ์
["is","the","blue"]
