Giả sử chúng ta có một mảng các số nguyên có kích thước là N và một khóa K. Nhiệm vụ của chúng ta là in ra K phần tử thường xuyên nhất của mảng. Ví dụ,
Đầu vào-1 -
N = 6
K = 2
arr[ ] = {1 ,1, 1, 2, 2, 3} Đầu ra -
1 2
Giải thích - Trong mảng số nguyên đã cho, K =2 phần tử đứng đầu có tần suất xuất hiện nhiều nhất trong mảng là {1,2}.
Đầu vào-2 -
N = 2
K = 1
arr[ ] = {1, 2} Đầu ra -
1
Giải thích - Trong mảng số nguyên đã cho, phần tử K =1 hàng đầu có tần suất xuất hiện nhiều nhất trong mảng là {1}.
Phương pháp tiếp cận để giải quyết vấn đề này
Trong mảng số nguyên đã cho, chúng ta phải tìm và trả về những số lặp lại hầu hết thời gian trong mảng đã cho. Khóa K hiển thị K phần tử trên cùng của mảng mà chúng ta phải trả về khi duyệt qua mảng.
Cách tiếp cận rất đơn giản. Chúng tôi sẽ tạo một bảng băm với một khóa là phần tử hiện tại và một giá trị là sự xuất hiện của số cụ thể đó. Sau khi sắp xếp toàn bộ bản đồ và tìm số lần xuất hiện của từng phần tử, hãy trả về kết quả đầu ra của K phần tử thường xuyên nhất đầu tiên.
-
Lấy N làm Đầu vào và mảng gồm N phần tử.
-
Một hàm topKfrequent (int * arr, int k) nhận arr [] và khóa K làm Đầu vào và trả về K phần tử thường xuyên hàng đầu.
-
Tạo một bản đồ băm của tất cả các phần tử và sự xuất hiện của chúng dưới dạng khóa và cặp.
-
Sắp xếp tất cả các giá trị trong bản đồ băm.
-
Hàm trợ giúp bool giúp sắp xếp bản đồ theo các giá trị và trả về các giá trị theo thứ tự giảm dần.
-
Lặp lại tất cả các giá trị trong bản đồ băm và trả về K phần tử thường xuyên nhất trong mảng đã cho.
Ví dụ
#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;
} Đầu ra
Chạy đoạn mã trên sẽ tạo ra kết quả sau,
2 1
Trong mảng số nguyên đã cho, K =2 phần tử thường xuyên nhất là 2, 1.