Hiểu bài toán

Bài toán yêu cầu tìm tần suất xuất hiện lớn nhất của một giá trị trong dãy số, nhưng chỉ xét các giá trị có tần suất không vượt quá một ngưỡng cho trước M.

Cụ thể:

• Input: N (số phần tử), M (giới hạn tần suất), và một dãy A gồm N số nguyên.
• Output: Tìm số lần xuất hiện nhiều nhất (tần suất cao nhất) của một giá trị bất kỳ trong dãy, sao cho tần suất đó phải nhỏ hơn hoặc bằng M.

Ví dụ: N=5, M=2, A = [1, 2, 2, 3, 3]

• Tần suất của 1 là 1 (<= 2).
• Tần suất của 2 là 2 (<= 2).
• Tần suất của 3 là 2 (<= 2).
• Max là 2.

Các cách tiếp cận

Cách Sử dụng Map (STL)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    freopen("SHIPPER.INP", "r", stdin);
    freopen("SHIPPER.OUT", "w", stdout);
    int n, m, maxx = 0;
    cin >> n >> m;
    vector<long long> a(n);
    for(int i = 0; i < n; i++) cin>>a[i];
    map<long long, int> p;
    for(auto x : a) 
    {
        p[x]++;
    }
    for(auto z : p)
    {
        if(z.second <= m) maxx = max(maxx, z.second);
    }
    cout<<maxx;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Phương pháp này sử dụng map của C++ STL để lưu trữ tần suất của các phần tử.

1. Đọc dữ liệu vào N, M và dãy số.
2. Duyệt qua dãy số, với mỗi phần tử, cập nhật tần suất của nó vào map. Phép cập nhật p[x]++ trong map mất O(log K) (với K là số phần tử duy nhất hiện tại).
3. Sau khi đếm xong, duyệt qua các cặp (key, value) trong map.
4. Kiểm tra nếu tần suất (value) <= M thì cập nhật lại kết quả lớn nhất (maxx).
5. Ưu điểm: Đơn giản, dễ code, xử lý được số rất lớn (long long) mà không cần mảng bù.
6. Nhược điểm: Tốc độ chậm hơn mảng bù do dùng cấu trúc cây.

Cách Sử dụng Mảng bù (Frequency Array)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Max 1000009
ll a[Max], dd[Max];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (fopen("SHIPPER.inp","r")){
        freopen("SHIPPER.inp","r",stdin);
        freopen("SHIPPER.out","w",stdout);
    }
    ll n,m;
    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        dd[a[i]]++;
    }
    ll gmax=-1;
    for(ll i=1;i<=n;i++){
        if(dd[i]<=m){
            if(dd[i]>gmax){
                gmax=dd[i];
            }
        }
    }
    cout<<gmax;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Phương pháp này sử dụng một mảng dd (mảng bù) để đếm tần suất.

1. Khai báo mảng dd với kích thước cố định (ví dụ 10^6).
2. Khi đọc từng số x từ dãy A, ta tăng dd[x] lên 1. Phép này mất O(1).
3. Sau khi đếm xong, duyệt mảng dd từ 1 đến N (hoặc giới hạn của giá trị) để tìm tần suất lớn nhất nhỏ hơn hoặc bằng M.
4. Ưu điểm: Tốc độ rất nhanh (O(N)), đơn giản.
5. Nhược điểm: Chỉ hoạt động tốt khi giá trị các phần tử nằm trong một khoảng nhỏ và xác định trước (ví dụ A[i] <= 10^6). Nếu giá trị quá lớn (10^9) hoặc âm, mảng không thể khai báo.

Cách Hash Map (unordered_map)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
  if(fopen("SHIPPER.inp","r"))
  {
    freopen("SHIPPER.inp","r",stdin);
    freopen("SHIPPER.out","w",stdout);
  }
  ll n,k;
  cin>>n>>k;
  unordered_map<ll,int> a;
  for(int i=1;i<=n;i++)
  {
    ll x;
    cin>>x;
    a[x]++;
  }
  ll gmax=0;
  for(auto x:a)
  {
    if(x.second>gmax&&x.second<=k)
    {
      gmax=x.second;
    }
  }
  cout<<gmax;

}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là biến thể của cách dùng Map, nhưng sử dụng unordered_map (băm).

1. Tương tự như map, unordered_map lưu trữ cặp key-value.
2. Tuy nhiên, unordered_map sử dụng bảng băm (hash table), cho phép truy cập và cập nhật với độ phức tạp trung bình là O(1).
3. Độ phức tạp tổng thể trung bình là O(N).
4. Ưu điểm: Nhanh hơn map (cố định O(1) so với O(log N)), tự xử lý được số lớn.
5. Nhược điểm: Có thể mất nhiều bộ nhớ hơn so với mảng bù, và trong trường hợp xấu nhất (xung đột băm) độ phức tạp có thể xấu.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán này về bản chất là tìm max(tần suất) trong các tần suất thỏa mãn điều kiện.
• Phương pháp Hashing (Map/Hash Map) là linh hoạt nhất cho các bài toán đếm tần suất khi giá trị đầu vào lớn hoặc không xác định.
• Nếu giá trị đầu vào nhỏ và nằm trong khoảng cố định, Mảng bù (Frequency Array) là cách hiệu quả nhất về tốc độ và độ ổn định.

Lỗi thường gặp

• Quên kiểm tra điều kiện tần suất <= M khi cập nhật kết quả max.
• Sử dụng mảng bù với giá trị đầu vào lớn (ví dụ 10^9) gây tràn bộ nhớ (Memory Limit Exceeded) hoặc lỗi truy cập mảng (Runtime Error).
• Bỏ qua việc khởi tạo biến max (hoặc khởi tạo sai, ví dụ 0 trong khi tần suất có thể là số âm - mặc dù bài này không có số âm).