Hướng dẫn giải của [200 đề thầy Đức] Bài 178: Tần số
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đếm số lần xuất hiện của mỗi giá trị trong dãy N số (N ≤ 10^5, |A[i]| ≤ 100), rồi in ra các giá trị có tần số lớn nhất, theo thứ tự tăng dần, cách nhau bởi dấu cách.
Sub 1: Vét cạn — ~O(N^2)~
Với mỗi phần tử A[i], quét toàn bộ dãy để đếm số lần A[i] xuất hiện. Lấy tần số lớn nhất, rồi thu các giá trị đạt tần số đó vào một set để tự động sắp xếp và loại trùng. Đạt 16/20 test, 4 test còn lại quá giờ vì N lớn làm số phép so sánh lên tới 10^10.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
// Vét cạn: với mỗi phần tử, đếm số lần xuất hiện bằng cách quét cả dãy
vector<int> freq(n);
for (int i = 0; i < n; i++) {
int c = 0;
for (int j = 0; j < n; j++)
if (a[j] == a[i]) c++;
freq[i] = c;
}
int mx = *max_element(freq.begin(), freq.end());
// Thu các giá trị có tần số lớn nhất, sắp tăng dần và loại trùng
set<int> res;
for (int i = 0; i < n; i++)
if (freq[i] == mx) res.insert(a[i]);
bool first = true;
for (int v : res) {
if (!first) cout << ' ';
cout << v;
first = false;
}
cout << "\n";
return 0;
}
Sub 2: Mảng đếm — ~O(N)~
Vì |A[i]| ≤ 100 nên chỉ có 201 giá trị khả dĩ. Dùng mảng cnt với chỉ số lệch +100 để đếm trong một lần đọc dữ liệu. Sau đó duyệt giá trị từ -100 đến 100 theo thứ tự tăng dần và in những giá trị có cnt bằng tần số lớn nhất. Cách duyệt này tự nhiên cho thứ tự đúng nên không cần sắp xếp. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// |A[i]| <= 100 nên dùng mảng đếm với chỉ số lệch +100
vector<int> cnt(201, 0);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x + 100]++;
}
int mx = *max_element(cnt.begin(), cnt.end());
bool first = true;
// Duyệt theo giá trị tăng dần để có thứ tự đúng
for (int v = -100; v <= 100; v++) {
if (cnt[v + 100] == mx) {
if (!first) cout << ' ';
cout << v;
first = false;
}
}
cout << "\n";
return 0;
}
Bình luận