Thuật toán tìm phần tử nhỏ nhất và nhỏ nhì trong một mảng với C++

Xét ví dụ sau:

Đầu vào: arr [] = {12, 13, 1, 10, 34, 1}
Đầu ra: Phần tử nhỏ nhất là 1 và
        Phần tử nhỏ nhì là 10

– Thuật toán Đơn giản nhất là sắp xếp mảng theo thứ tự tăng dần. Hai phần tử đầu tiên trong mảng đã sắp xếp sẽ là hai phần tử nhỏ nhất. Độ phức tạp thời gian của giải pháp này là O(nLog n).
– Thuật toán thứ 2 là duyệt mảng hai lần. Trong lần duyệt đầu tiên, tìm phần tử tối thiểu. Cho phần tử này là x. Trong lần duyệt thứ hai, tìm phần tử nhỏ nhất lớn hơn x. Độ phức tạp thời gian của giải pháp này là O(n).
Giải pháp trên yêu cầu hai truyền của mảng đầu vào.
– Thuật toán thứ 3 chúng ta có thể tìm thấy hai yếu tố tối thiểu trong một lần duyệt.
Thuật toán như sau:

1) Khởi tạo cả hai giá trị nhỏ nhất và nhỏ nhì dưới dạng INT_MAX
    nhỏ nhất = nhỏ nhì = INT_MAX
2) Duyệt qua tất cả các phần tử.
   a) Nếu phần tử thứ i nhỏ hơn phần tử nhỏ nhất, thì cập nhật phần tử nhỏ nhất 
và nhỏ nhì.
   b) Nếu phần tử thứ i nhỏ hơn phần tử thứ hai nhưng khác phần tử thứ nhất thì 
cập nhật phần tử thứ hai

Code tham khảo cho thuật toán:

#include <bits/stdc++.h>
using namespace std; 
void nhoNhatNhi(int arr[], int arr_size) {
    int i, first, second; 
    /* Cần nhập vào ít nhất 2 phần tử */
    if (arr_size < 2) {
        cout << " Invalid Input ";
        return;
    } 
    first = second = INT_MAX;
    for (i = 0; i < arr_size ; i ++) {
        // Nếu phần tử thứ i nhỏ hơn first:
        if (arr[i] < first)  {
            second = first;
            first = arr[i];
        } 
        // Nếu phần tử thứ i nhỏ hơn second và khác first:
        else if (arr[i] < second && arr[i] != first)
            second = arr[i];
    }
    if (second == INT_MAX)
        cout << "Khong ton tai phan tu nho thu 2\n";
    else
        cout << "Phan tu nho nhat: " << first << endl <<
            "Phan tu nho thu hai: " << second << endl;
}
int main() {
    int arr[] = {12, 13, 1, 10, 34, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    nhoNhatNhi(arr, n);
    return 0;
}

Với thuật toán trên, độ phức tạp là O(n).

Xử lý bài toán không cần sử dụng hàm:

#include <iostream>
using namespace std;
 
int main () {
    freopen("MAX2.INP","r",stdin);
    freopen("MAX2.OUT","w",stdout);
    int n, a[10000], min1, min2;
    // Doc so luong phan tu n:
    cin >> n;
    // Doc mang a:
    for (int i = 0; i < n; i++)
        cin >> a[i];
    // Gan cho min1, min2:
    min1 = min2 = INT_MAX;
    for (int i = 0; i < n; i++) {
        // Neu phan tu thu i nho hon min1:
        if (a[i] < min1) {
            min2 = min1;
            min1 = a[i];
        }
        // Neu phan tu thu i < min2 va khac min1:
        else if (a[i] < min2 && a[i] != min1)
            min2 = a[i];
    }
    // Truong hop ko ton tai min2 (day so bang nhau)
    if (min2 == min1)
        cout << -1;
    // Neu ton tai min2 thi tim vi tri cua no:
    else
        for (int i = 0; i < n; i++)
            if (a[i] == min2)
                cout << i + 1 << " ";
    return 0;
}

Bạn có thể làm bài tương tự: Số lớn thứ 2 của mảng ở đây

Cùng chuyên mục