Hướng dẫn giải của Đội tình nguyện viên
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm chiều cao xuất hiện nhiều nhất trong danh sách n học sinh. Nếu có nhiều chiều cao cùng tần suất xuất hiện cao nhất, ta cần chọn chiều cao lớn hơn trong số đó. Nói cách khác, ta cần tìm cặp (chiều cao, sốlượng) thỏa mãn: (1) sốlượng là lớn nhất có thể, và (2) nếu có nhiều chiều cao cùng có số_lượng này, chọn chiều cao lớn nhất.
Các cách tiếp cận
Cách Hash Map (Sử dụng bảng băm)
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
unordered_map<int, int> freq;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
freq[x]++;
}
int bestHeight = 0;
int bestCount = 0;
for (auto const& [height, count] : freq) {
if (count > bestCount || (count == bestCount && height > bestHeight)) {
bestCount = count;
bestHeight = height;
}
}
cout << bestHeight << " " << bestCount << endl;
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Sử dụng một bảng băm (hash map) để đếm tần suất của từng chiều cao. Duyệt qua bảng băm để tìm chiều cao có số lần xuất hiện nhiều nhất, ưu tiên chiều cao lớn hơn nếu bằng số lượng. Cách này hiệu quả về mặt thời gian O(n) nhưng cần bộ nhớ O(n).
Cách Sắp xếp và đếm (Sorting)
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int main() {
int n;
scanf("%d", &n);
int *a = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
qsort(a, n, sizeof(int), cmp);
int bestHeight = a[0];
int bestCount = 1;
int currCount = 1;
for (int i = 1; i < n; i++) {
if (a[i] == a[i-1]) {
currCount++;
} else {
if (currCount > bestCount || (currCount == bestCount && a[i-1] > bestHeight)) {
bestCount = currCount;
bestHeight = a[i-1];
}
currCount = 1;
}
}
// Kiểm tra dãy cuối cùng
if (currCount > bestCount || (currCount == bestCount && a[n-1] > bestHeight)) {
bestCount = currCount;
bestHeight = a[n-1];
}
printf("%d %d\n", bestHeight, bestCount);
free(a);
return 0;
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)
Sắp xếp mảng chiều cao tăng dần. Các phần tử giống nhau sẽ đứng cạnh nhau. Duyệt một lần để đếm số lượng phần tử liên tiếp bằng nhau. Luôn cập nhật kết quả tốt nhất (nhiều nhất -> lớn nhất) trong quá trình duyệt. Đây là cách tiếp cận phổ biến và dễ hiểu.
Cách Tối ưu hóa (Optimized)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<int> h(n);
for (int i = 0; i < n; i++) {
cin >> h[i];
}
sort(h.begin(), h.end());
int maxH = h[0];
int maxC = 1;
int currC = 1;
for (int i = 1; i < n; i++) {
if (h[i] == h[i-1]) {
currC++;
} else {
if (currC > maxC || (currC == maxC && h[i-1] > maxH)) {
maxC = currC;
maxH = h[i-1];
}
currC = 1;
}
}
if (currC > maxC || (currC == maxC && h[n-1] > maxH)) {
maxC = currC;
maxH = h[n-1];
}
cout << maxH << " " << maxC << endl;
return 0;
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)
Phiên bản C++ sử dụng vector và hàm sort chuẩn. Logic xử lý tương tự Approach 2. Việc sử dụng vector giúp quản lý bộ nhớ an toàn hơn so với mảng thường trong C. Độ phức tạp vẫn là O(n log n) do thao tác sắp xếp.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n) | O(n) | Hash Map (Sử dụng bảng băm) |
| 2 | O(n log n) | O(n) | Sắp xếp và đếm (Sorting) |
| 3 | O(n log n) | O(n) | Tối ưu hóa (Optimized) |
Bài học kinh nghiệm
- Bài toán có thể giải quyết bằng cách đếm tần suất (frequency counting). Yêu cầu 'nhiều nhất -> lớn nhất' có thể được xử lý ngay trong bước cập nhật kết quả.
- Nếu dữ liệu đầu vào lớn (n ~ 10^5) nhưng giá trị nhỏ, có thể dùng mảng đếm (counting sort) để đạt O(n). Tuy nhiên, với giá trị lên tới 10^9, việc dùng Hash Map hoặc Sắp xếp là bắt buộc.
- Khi duyệt mảng đã sắp xếp, ta cần chú ý xử lý đoạn cuối cùng của mảng (phần tử cuối cùng) vì vòng lặp for thường dừng ở n-1.
Lỗi thường gặp
- Quên kiểm tra điều kiện 'chiều cao lớn hơn' khi số lượng bằng nhau, dẫn đến kết quả sai (ví dụ chọn 155 thay vì 156 dù cùng tần suất).
- Lỗi truy cập ngoài mảng (out of bounds) khi duyệt mảng, đặc biệt với trường hợp n=1.
- Sử dụng kiểu dữ liệu quá nhỏ (ví dụ
shorthoặcintcơ bản) cho giá trịh_inếu giá trị đầu vào lớn, nhưng trong bài nàyintlà đủ. - Không xử lý đúng dãy cuối cùng khi duyệt mảng đã sắp xếp (ví dụ: 1 1 2 2, nếu chỉ kiểm tra khi
a[i] != a[i-1], dãy 2 có thể bị bỏ qua nếu không có phần tử 'kế tiếp' để so sánh).
Bình luận