Hướng dẫn giải của Số lớn thứ 3
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
, , ,
Editorial for ptit062: Số lớn thứ 3
Hiểu bài toán
Bài toán yêu cầu tìm số lớn thứ 3 trong một dãy số và in ra vị trí xuất hiện đầu tiên của nó (index bắt đầu từ 1). Nếu dãy số không có đủ 3 số khác nhau để tạo ra số lớn thứ 3, ta phải in ra thông báo 'Khong the tim duoc!'. Vấn đề quan trọng cần lưu ý là cách xử lý các số trùng lặp: ta cần tìm số lớn thứ 3 duy nhất, tức là loại bỏ các số trùng nhau trước khi xác định thứ tự xếp hạng.
Các cách tiếp cận
Cách Sắp xếp và loại bỏ trùng lặp
#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a, const void *b) {
int x = *(int*)a;
int y = *(int*)b;
return y - x; // Sắp xếp giảm dần
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
int n;
scanf("%d",&n);
int a[100005], c[100005];
for (int i = 0; i < n; i++) {
scanf("%d",&a[i]);
c[i] = a[i];
}
// Sắp xếp mảng phụ c
qsort(c, n, sizeof(int), cmp);
int distinct_count = 0;
int third_val;
// Tìm 3 số khác nhau đầu tiên sau khi sắp xếp
for (int i = 0; i < n; i++) {
if (i == 0 || c[i] != c[i-1]) {
distinct_count++;
if (distinct_count == 3) {
third_val = c[i];
break;
}
}
}
if (distinct_count < 3) {
printf("Khong the tim duoc!\n");
} else {
// Tìm vị trí đầu tiên trong mảng gốc
for (int i = 0; i < n; i++) {
if(a[i] == third_val) {
printf("%d %d\n", third_val, i + 1);
break;
}
}
}
}
return 0;
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)
Cách tiếp cận này sử dụng một mảng phụ và hàm qsort để sắp xếp dãy số theo thứ tự giảm dần. Sau đó, ta duyệt qua mảng đã sắp xếp để tìm 3 số khác nhau đầu tiên (số đầu tiên là lớn nhất, số thứ hai là lớn thứ hai, số thứ ba là lớn thứ ba). Sau khi xác định được giá trị của số lớn thứ ba, ta quay lại mảng ban đầu để tìm vị trí xuất hiện đầu tiên của nó. Cách này dễ hiểu và dễ cài đặt nhưng tốn kém thời gian và bộ nhớ do phải sắp xếp toàn bộ dãy số.
Cách Duyệt một lần (One Pass)
#include <stdio.h>
int main(){
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
// Khởi tạo giá trị nhỏ hơn bất kỳ số nào trong dãy (-100000)
int first = -1000000;
int second = -1000000;
int third = -1000000;
for(int i=0;i<n;i++){
// Bỏ qua nếu số đó đã xuất hiện trong top 3 (trùng lặp)
if(a[i]==first || a[i]==second || a[i]==third) continue;
if(a[i] > first){
third = second;
second = first;
first = a[i];
}
else if(a[i] > second){
third = second;
second = a[i];
}
else if(a[i] > third){
third = a[i];
}
}
// Nếu giá trị third vẫn là giá trị khởi tạo (hoặc nhỏ hơn ngưỡng cho phép)
// Ta cần kiểm tra xem có tìm thấy đủ 3 số distinct không
// Ở đây sử dụng lại mảng a để tìm index
if(third <= -1000000) printf("Khong the tim duoc!\n");
else{
for(int i=0;i<n;i++){
if(a[i]==third){
printf("%d %d\n",third,i+1);
break;
}
}
}
}
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Đây là phương pháp tối ưu nhất. Ta duyệt qua mảng một lần duy nhất để tìm ra 3 giá trị lớn nhất khác nhau. Ta sử dụng 3 biến first, second, và third để lưu giá trị và cập nhật chúng khi gặp số mới lớn hơn. Điều kiện if(a[i] == first || a[i] == second || a[i] == third) continue; rất quan trọng để đảm bảo ta chỉ xét các số khác nhau (distinct). Sau khi có giá trị third, ta duyệt mảng ban đầu một lần nữa để lấy vị trí. Phương pháp này giúp giảm thời gian chạy đáng kể so với việc sắp xếp.
Cách Duyệt một lần (Lưu vị trí)
#include <stdio.h>
void thirdh(int *a, int size, int *p){
int one = -10000000, two = -10000000, three = -10000000;
int temp1 = -1, temp2 = -1, temp3 = -1;
for(int i = 0; i < size; i++){
if(a[i] > one){
three = two;
temp3 = temp2;
two = one;
temp2 = temp1;
one = a[i];
temp1 = i;
}
else if(a[i] > two && a[i] < one){
three = two;
temp3 = temp2;
two = a[i];
temp2 = i;
}
else if(a[i] > three && a[i] < two){
three = a[i];
temp3 = i;
}
}
p[0] = three; // Gia tri
p[1] = temp3 + 1; // Vi tri (1-based)
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int size, ans[2];
scanf("%d", &size);
int arr[size];
for(int j = 0; j < size; j++)
scanf("%d", &arr[j]);
thirdh(arr, size, ans);
if(ans[0] <= -10000000)
printf("Khong the tim duoc!\n");
else
printf("%d %d\n", ans[0], ans[1]);
}
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(1)
Đây là biến thể của phương pháp One Pass. Thay vì chỉ tìm giá trị rồi tìm lại vị trí, phương pháp này lưu luôn vị trí index của first, second, và third ngay trong quá trình duyệt. Điều này giúp loại bỏ vòng lặp thứ hai để tìm index, từ đó tối ưu hơn về mặt thời gian thực thi (dù độ phức tạp thuật toán vẫn là O(n)). Tuy nhiên, code sẽ phức tạp hơn một chút do phải quản lý nhiều biến trạng thái hơn.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n log n) | O(n) | Sắp xếp và loại bỏ trùng lặp |
| 2 | O(n) | O(n) | Duyệt một lần (One Pass) |
| 3 | O(n) | O(1) | Duyệt một lần (Lưu vị trí) |
Bài học kinh nghiệm
- Bài toán yêu cầu số lớn thứ 3 'duy nhất', nghĩa là các số trùng lặp phải được coi là một. Ví dụ: 5, 4, 4, 3 thì số lớn thứ 3 là 3 (sau 5 và 4).
- Vị trí cần tìm là vị trí xuất hiện đầu tiên trong dãy số ban đầu, không phải trong dãy đã sắp xếp.
Lỗi thường gặp
- Lầm tưởng rằng chỉ cần tìm giá trị thứ 3 trong mảng đã sắp xếp là xong, mà không xử lý việc loại bỏ các số trùng lặp.
- Bỏ qua trường hợp dãy số có ít hơn 3 số khác nhau (ví dụ: [2, 2, 2] hoặc [1, 2]).
- Sử dụng số quá lớn hoặc quá nhỏ để khởi tạo biến so sánh mà không chắc chắn về phạm vi giá trị đầu vào (-10^5 đến 10^5).
Bình luận