Chương trình C++ tìm phần tử nhỏ thứ hai (O(n))

Tìm phần tử nhỏ thứ hai trong mảng với độ phức tạp O(n) bằng cách duyệt một lần, giữ track hai giá trị nhỏ nhất.

Thuật toán

SecondSmallest(a[], n):
  s1 = s2 = INT_MAX.
  Với mỗi phần tử x:
    Nếu x < s1: s2 = s1; s1 = x.
    Ngược lại nếu x < s2 và x != s1: s2 = x.
  Nếu s2 == INT_MAX: in "Khong co phan tu nho thu 2".
  Ngược lại: in s2.

Ví dụ mã nguồn

#include <iostream>
#include <climits>
using namespace std;

void secondSmallest(int a[], int n) {
    int s1 = INT_MAX, s2 = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (a[i] < s1) { s2 = s1; s1 = a[i]; }
        else if (a[i] < s2 && a[i] != s1) s2 = a[i];
    }
    if (s2 == INT_MAX) cout << "Khong co phan tu nho thu 2";
    else cout << "Phan tu nho thu 2: " << s2;
}

int main() {
    int n;
    cout << "So phan tu: "; cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cout << "Phan tu " << i+1 << ": "; cin >> a[i];
    }
    secondSmallest(a, n);
    return 0;
}

Đầu ra mẫu

So phan tu: 5
Phan tu: 1 2 1 3 4
Phan tu nho thu 2: 2