สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มขนาด 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 ด้านบนของอาร์เรย์ที่เราต้องส่งคืนขณะสำรวจอาร์เรย์
วิธีการนั้นง่ายมาก เราจะสร้างตารางแฮชที่มีคีย์เป็นองค์ประกอบปัจจุบันและค่าเป็นตัวเลขที่เกิดขึ้น หลังจากจัดเรียงแผนที่ทั้งหมดและค้นหาการเกิดขึ้นขององค์ประกอบแต่ละรายการแล้ว ให้ส่งคืนผลลัพธ์ขององค์ประกอบ K รายการแรกที่มีความถี่สูงสุด
-
รับ N เป็นอินพุตและอาร์เรย์ขององค์ประกอบ N
-
ฟังก์ชัน topKfrequent(int *arr, int k) ที่รับ arr[ ] และคีย์ K เป็นอินพุตและส่งกลับองค์ประกอบความถี่ K บนสุด
-
สร้าง hashmap ขององค์ประกอบทั้งหมดและเหตุการณ์ที่เกิดขึ้นเป็นคีย์และคู่
-
จัดเรียงค่าทั้งหมดใน hashmap
-
ฟังก์ชันตัวช่วยบูลช่วยในการจัดเรียงแผนที่ตามค่าและส่งกลับค่าในลำดับจากมากไปน้อย
-
วนซ้ำค่าทั้งหมดใน 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[nums[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,k);
return 0;
} ผลลัพธ์
การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์ดังต่อไปนี้
2 1
ในอาร์เรย์ของจำนวนเต็มที่กำหนด องค์ประกอบ K=2 ที่บ่อยที่สุดคือ 2, 1
