สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มขนาด N และกุญแจ K งานของเราคือพิมพ์องค์ประกอบที่เกิดบ่อยที่สุด K อันดับแรกของอาร์เรย์ ตัวอย่างเช่น
ตัวอย่างอินพุต 1
N = 6, K = 2, arr[] = {1, 1, 1, 2, 2, 3}
เอาต์พุต
1 2
คำอธิบาย
ในอาร์เรย์ของจำนวนเต็มที่กำหนด องค์ประกอบ K=2 อันดับแรกที่ความถี่มากที่สุดในอาร์เรย์คือ {1, 2}
ตัวอย่างอินพุต 2
N = 2, K = 1, arr[] = {1, 2}
เอาต์พุต
1
คำอธิบาย
ในอาร์เรย์ของจำนวนเต็มที่กำหนด องค์ประกอบ K=1 อันดับแรกที่ความถี่มากที่สุดในอาร์เรย์คือ {1}
วิธีการแก้ปัญหา
ในอาร์เรย์ของจำนวนเต็มที่กำหนด เราต้องหาและคืนค่าตัวเลขเหล่านั้นที่ซ้ำมากที่สุดในอาร์เรย์ที่กำหนด กุญแจ K แสดงถึงองค์ประกอบ K อันดับแรกของอาร์เรย์ที่เราต้องคืนค่าขณะวนลูปผ่านอาร์เรย์
วิธีการค่อนข้างง่าย เราจะสร้าง hash table ด้วย key เป็นองค์ประกอบปัจจุบันและ value เป็นจำนวนครั้งที่เกิดขึ้นของตัวเลขนั้นๆ หลังจากจัดเรียงทั้ง map และหาจำนวนครั้งที่เกิดขึ้นของแต่ละองค์ประกอบ คืนค่าผลลัพธ์เอาต์พุทของ K องค์ประกอบที่เกิดบ่อยที่สุด
- รับ N เป็นอินพุตและอาร์เรย์ของ N องค์ประกอบ
- ฟังก์ชัน topKfrequent(int *arr, int k) ที่รับ arr[] และกุญแจ K เป็นอินพุตและคืนค่าองค์ประกอบที่เกิดบ่อยที่สุด K อันดับแรก
- สร้าง hashmap ของทุกองค์ประกอบและจำนวนครั้งที่เกิดขึ้นเป็น key และ pair
- จัดเรียงค่าทั้งหมดใน hashmap
- ฟังก์ชัน bool helper ช่วยจัดเรียง map ตามค่าและคืนค่าค่าลำดับลดลง
- วนลูปผ่านค่าทั้งหมดใน hashmap และคืนค่าองค์ประกอบที่เกิดบ่อยที่สุด K อันดับแรกในอาร์เรย์ที่กำหนด
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
bool compare(pair<int, int> &a, pair<int, int> &b) {
return a.second > b.second;
}
void topKfrequent(int *arr, int n, int k) {
unordered_map<int, int> mp;
for (int i = 0; i < n; i++) {
mp[arr[i]]++;
}
vector<pair<int, int>> v(mp.begin(), mp.end());
sort(v.begin(), v.end(), compare);
for (int i = 0; i < k; i++) {
cout << v[i].first << " ";
}
}
int main() {
int N = 5;
int arr[N] = {1, 1, 3, 2, 2};
int k = 2;
topKfrequent(arr, N, k);
return 0;
}
ผลลัพธ์
การรันโค้ดด้านบนจะสร้างเอาต์พุตดังนี้
2 1
ในอาร์เรย์ของจำนวนเต็มที่กำหนด องค์ประกอบที่เกิดบ่อยที่สุด K=2 อันดับแรกคือ 2, 1
