Giả sử chúng ta có một mảng các số nguyên có kích thước N. Nhiệm vụ là tìm phần tử xuất hiện nhiều nhất trong mảng các số nguyên đã cho. Ví dụ:
Đầu vào-1 -
N = 8
A[ ] = {1,2,4,3,3,1,1,5} Đầu ra -
1
Giải thích - Trong mảng các số nguyên đã cho, số xuất hiện nhiều nhất là ‘1’. Do đó, đầu ra là "1".
Đầu vào-2 -
N = 6
A[ ] = {1,4,4,4,1,1} Đầu ra-a -
1
Đầu ra-b -
4
Giải thích:Trong mảng các số nguyên đã cho, số xuất hiện nhiều nhất là ‘1’ và ‘4’. Vì vậy, chúng tôi có thể trả lại đầu ra cho bất kỳ một trong số chúng.
Phương pháp tiếp cận để giải quyết vấn đề này
Mảng đã cho chứa nhiều số nguyên trong đó chúng ta phải tìm phần tử xuất hiện nhiều nhất trong mảng. Để giải quyết vấn đề này trong thời gian tuyến tính O (n) và Không gian tuyến tính O (n), chúng ta có thể sử dụng cách tiếp cận của một bản đồ băm.
Trong cách tiếp cận này, chúng tôi sẽ tạo một bản đồ không có thứ tự (Thư viện STL) bao gồm cặp khóa-giá trị trong đó khóa sẽ là một phần tử và Giá trị sẽ là sự xuất hiện của phần tử. Trong khi duyệt qua bản đồ, chúng tôi sẽ tìm thấy số lượng xuất hiện tối đa và trả về số đó dưới dạng Đầu ra.
-
Lấy Đầu vào một mảng có kích thước N.
-
Hàm số nguyên maxOcchood (int A [], int size) nhận một mảng và kích thước của nó làm đầu vào và trả về các số có tần suất tối đa.
-
Tạo một bản đồ băm của tất cả các phần tử của mảng bằng cách lấy khóa làm phần tử và giá trị làm tần số của nó.
-
Lặp lại bản đồ và kiểm tra xem có phần tử nào có tần suất xuất hiện nhiều nhất hay không rồi trả về kết quả là số. Ngược lại, nếu không có bất kỳ số nào trong mảng thì trả về ‘-1’.
Ví dụ
#include<bits/stdc++.h>
using namespace std;
int maxOccurrence(int A[], int size){
int mxcount=0;
int res=-1;
unordered_map<int,int>mp;
for(int i=0;i<size;i++){
mp[A[i]]++;
}
for(auto x:mp){
if(x.second>mxcount){
res= x.first;
mxcount=x.second;
}
}
return res;
}
int main(){
int N=6;
int A[N]= {1,4,4,4,2,1};
int ans= maxOccurrence(A,N);
cout<<ans<<endl;
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ in ra kết quả là,
4
4 có tần số là 3, là tần số lớn nhất từ tất cả các số khác trong mảng đã cho.