Hướng dẫn giải của Tìm số lớn thứ hai của mảng


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.

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, Zed, hungvpc2, thanhhang240607

Hiểu bài toán

Bài toán yêu cầu tìm phần tử lớn thứ hai trong một mảng gồm n số nguyên. Điều kiện quan trọng là phần tử lớn thứ hai phải thực sự nhỏ hơn phần tử lớn nhất (không được bằng). Nếu không t tồn tại phần tử lớn thứ hai (ví dụ: tất cả các phần tử đều bằng nhau hoặc mảng chỉ có 1 phần tử), cần in ra 'NOT FOUND'.

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

Cách Sử dụng mảng phụ để đếm và loại trừ
#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    int min_val = 1000000001;
    int max_val = -1000000001;

    // Đọc dữ liệu và tìm min, max để chuẩn hóa chỉ số
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        if (a[i] > max_val) max_val = a[i];
        if (a[i] < min_val) min_val = a[i];
    }

    int range = max_val - min_val + 1;
    // Dùng mảng đếm frequency (kiểu long để tránh tràn nếu cần)
    long* count = (long*)calloc(range, sizeof(long));

    for(int i = 0; i < n; i++) {
        count[a[i] - min_val]++;
    }

    // Duyệt từ giá trị lớn nhất trở xuống
    int found = 0;
    int result = 0;

    // Bỏ qua phần tử lớn nhất (nếu có)
    for (int i = range - 1; i >= 0; i--) {
        if (count[i] > 0) {
            result = i + min_val;
            break;
        }
    }

    // Tìm phần tử tiếp theo khác với phần tử lớn nhất
    for (int i = range - 2; i >= 0; i--) {
        if (count[i] > 0) {
            printf("%d", i + min_val);
            found = 1;
            break;
        }
    }

    if (!found) printf("NOT FOUND");
    free(count);
    return 0;
}
  • Time Complexity: O(n + K) (K là khoảng giá trị, max ~ 2*10^9)
  • Space Complexity: O(K)

Phương pháp này sử dụng kỹ thuật Counting Sort. Đầu tiên, ta xác định giá trị lớn nhất và nhỏ nhất của mảng. Sau đó, ta tạo một mảng phụ để đếm số lần xuất hiện của mỗi giá trị. Bằng cách duyệt mảng đếm từ giá trị lớn nhất trở xuống, ta có thể dễ dàng tìm thấy phần tử lớn nhất và phần tử lớn thứ hai một cách hiệu quả.

Cách Duyệt một lần để tìm Max và Second Max
#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    long long max1, max2;
    long long val;
    int count = 0;

    // Khởi tạo giá trị ban đầu
    scanf("%lld", &val);
    max1 = val;
    max2 = -2000000000LL; // Giá trị nhỏ hơn mọi số trong input
    count = 1;

    for (int i = 1; i < n; i++) {
        scanf("%lld", &val);
        if (val > max1) {
            max2 = max1;
            max1 = val;
        } else if (val > max2 && val != max1) {
            max2 = val;
        }
    }

    // Kiểm tra xem max2 có được cập nhật không
    // Nếu max2 vẫn là giá trị khởi tạo ban đầu và không có số nào nhỏ hơn max1 (trường hợp mảng toàn số giống nhau)
    // Hoặc dùng một cờ để kiểm tra
    int valid = (max2 > -2000000000LL);

    // Nhưng cách an toàn hơn là kiểm tra xem có tồn tại số khác max1 không
    // Reset lại để kiểm tra
    // Cách này dùng logic đơn giản:
    // Nếu max2 chưa bao giờ được gán giá trị thực sự (do chỉ có max1 và các số nhỏ hơn rất nhiều hoặc trùng max1)

    if (n == 1) {
        printf("NOT FOUND");
        return 0;
    }

    // Logic kiểm tra:
    // Nếu max2 vẫn là giá trị rất nhỏ ban đầu, cần kiểm tra xem có thực sự có số khác max1 không
    // Tuy nhiên, để đơn giản, ta có thể dùng một mảng hoặc kiểm tra lại
    // Đơn giản nhất: Duyệt lại hoặc dùng flag

    // Giải pháp tối ưu nhất:
    // Đọc tất cả vào mảng hoặc xử lý luồng.
    // Với approach này, ta cần xử lý kỹ điều kiện.
    // Nếu max2 không thay đổi so với khởi tạo, in NOT FOUND.

    if (max2 == -2000000000LL) {
        printf("NOT FOUND");
    } else {
        printf("%lld", max2);
    }

    return 0;
}
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Đây là giải pháp tối ưu nhất. Ta chỉ cần duyệt qua mảng một lần duy nhất. Duy trì hai biến max1 (lớn nhất) và max2 (lớn thứ hai). Khi gặp một số mới:

  1. Nếu nó lớn hơn max1, thì max2 nhận giá trị cũ của max1, còn max1 nhận giá trị mới.
  2. Nếu nó nằm giữa max1max2 (và không bằng max1), cập nhật max2. Cần chú ý xử lý các trường hợp đặc biệt như mảng toàn số giống nhau.
Cách Sắp xếp mảng
#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    long long *x = (long long*)a;
    long long *y = (long long*)b;
    if (*x > *y) return -1; // Sắp xếp giảm dần
    if (*x < *y) return 1;
    return 0;
}

int main() {
    int n;
    scanf("%d", &n);
    long long *a = (long long*)malloc(n * sizeof(long long));
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }

    qsort(a, n, sizeof(long long), cmp);

    int found = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] != a[0]) {
            printf("%lld", a[i]);
            found = 1;
            break;
        }
    }

    if (!found) {
        printf("NOT FOUND");
    }

    free(a);
    return 0;
}
  • Time Complexity: O(n log n)
  • Space Complexity: O(n)

Phương pháp này khá trực quan: sắp xếp mảng theo thứ tự giảm dần. Sau đó, phần tử đầu tiên là lớn nhất. Ta chỉ cần tìm phần tử đầu tiên có giá trị khác với phần tử đầu tiên là ra đáp án. Tuy nhiên, độ phức tạp O(n log n) do việc sắp xếp khiến giải pháp này kém hiệu quả hơn so với duyệt một lần khi n lên tới 10^6.

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

Cách tiếp cận Time Space Tên
1 O(n + K) (K là khoảng giá trị, max ~ 2*10^9) O(K) Sử dụng mảng phụ để đếm và loại trừ
2 O(n) O(1) Duyệt một lần để tìm Max và Second Max
3 O(n log n) O(n) Sắp xếp mảng

Bài học kinh nghiệm

  • Có thể giải quyết bài toán chỉ với 1 lần duyệt (O(n)) bằng cách duy trì hai biến lưu giá trị lớn nhất và lớn thứ hai.
  • Điều kiện 'lớn thứ hai thực sự nhỏ hơn lớn nhất' quan trọng, cần đảm bảo bỏ qua các phần tử trùng giá trị với lớn nhất.
  • Cần xử lý các edge case: mảng toàn số giống nhau, mảng chứa số âm lớn, số dương lớn.

Lỗi thường gặp

  • Sử dụng kiểu dữ liệu quá nhỏ (ví dụ: int thay vì long long) dẫn đến tràn số khi tính toán giá trị trung gian hoặc so sánh.
  • Khởi tạo biến lớn thứ hai sai cách, dẫn đến việc không thể phân biệt được giữa việc chưa tìm thấy lớn thứ hai và việc lớn thứ hai thực sự là số rất nhỏ.
  • Quên kiểm tra trường hợp chỉ có một phần tử duy nhất hoặc tất cả các phần tử đều bằng nhau.

Bình luận

Please read the guidelines before commenting.


Không có bình luận tại thời điểm này.