Hướng dẫn giải của [200 đề thầy Đức] Bài 104: Phần tử lớn thứ nhì
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
Cần tìm số lớn thứ nhì trong dãy, trong đó các số bằng nhau được tính riêng (nếu số lớn nhất xuất hiện hai lần thì đáp án là chính nó).
Sub 1: Vét cạn so sánh từng cặp — ~O(n^2)~
Với mỗi a[i], đếm số phần tử lớn hơn nó (gt) và bằng nó (eq). a[i] là đáp án nếu gt = 1, hoặc gt = 0 và eq ≥ 2. Lấy giá trị lớn nhất thỏa điều kiện. Đạt 2/21 test, còn lại quá giờ.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Vét cạn O(n^2): với mỗi a[i], đếm số phần tử lớn hơn nó (gt) và bằng nó (eq).
// a[i] là số lớn thứ nhì nếu gt == 1, hoặc gt == 0 và eq >= 2 (max lặp lại).
long long ketQua = LLONG_MIN;
for (int i = 0; i < n; i++) {
int gt = 0, eq = 0;
for (int j = 0; j < n; j++) {
if (a[j] > a[i]) gt++;
else if (a[j] == a[i]) eq++;
}
if (gt == 1 || (gt == 0 && eq >= 2)) ketQua = max(ketQua, a[i]);
}
cout << ketQua << "\n";
return 0;
}
Sub 2: Duyệt một lần giữ hai số lớn nhất — ~O(n)~
Duyệt dãy, giữ m1 (lớn nhất) và m2 (lớn thứ nhì). Khi gặp x > m1 thì m2 = m1, m1 = x; nếu x ≤ m1 và x > m2 thì m2 = x. Cách này xử lý đúng các số bằng nhau. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// m1 = số lớn nhất, m2 = số lớn thứ nhì (tính cả số bằng nhau)
long long m1 = LLONG_MIN, m2 = LLONG_MIN;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
if (x > m1) { // x mới là số lớn nhất, số lớn nhất cũ trở thành thứ nhì
m2 = m1;
m1 = x;
} else if (x > m2) { // x nằm giữa m2 và m1 (hoặc bằng m1: khi đó m2 = m1)
m2 = x;
}
}
cout << m2 << "\n";
return 0;
}
Bình luận