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;
}

Tham khảo thêm:

Để tìm phần tử nhỏ nhất và nhỏ nhì trong một mảng, ta có thể sử dụng thuật toán sau đây:

Khởi tạo hai biến min1 và min2 với giá trị là phần tử đầu tiên và giá trị vô cùng lớn (để đảm bảo min2 lớn hơn tất cả các phần tử trong mảng).
Duyệt qua từng phần tử trong mảng.
Nếu phần tử hiện tại nhỏ hơn min1, thì gán min2 bằng min1 và gán min1 bằng phần tử hiện tại.
Nếu phần tử hiện tại lớn hơn hoặc bằng min1 và nhỏ hơn min2, thì gán min2 bằng phần tử hiện tại.
Sau khi duyệt qua tất cả các phần tử, min1 sẽ là phần tử nhỏ nhất, min2 sẽ là phần tử nhỏ nhì.

Dưới đây là mã giả của thuật toán trên:

int a[n];
int min1 = a[0];
int min2 = INT_MAX;

for (int i = 1; i < n; i++) {
    if (a[i] < min1) {
        min2 = min1;
        min1 = a[i];
    }
    else if (a[i] >= min1 && a[i] < min2) {
        min2 = a[i];
    }
}

cout << "Phan tu nho nhat: " << min1 << endl;
cout << "Phan tu nho nhi: " << min2 << endl;

Ở đây, mảng a có kích thước là n. Ban đầu, ta khởi tạo biến min1 bằng phần tử đầu tiên trong mảng và biến min2 bằng giá trị INT_MAX (được định nghĩa trong thư viện limits.h của C++ là giá trị lớn nhất mà kiểu dữ liệu int có thể chứa). Sau đó, chương trình duyệt qua các phần tử từ phần tử thứ hai đến phần tử cuối của mảng. Trong mỗi lần lặp, nếu phần tử hiện tại nhỏ hơn min1, chương trình gán min2 bằng min1 và gán min1 bằng phần tử hiện tại. Nếu phần tử hiện tại lớn hơn hoặc bằng min1 và nhỏ hơn min2, chương trình gán min2 bằng phần tử hiện tại. Sau khi duyệt qua tất cả các phần tử của mảng, chương trình sẽ in ra giá trị của phần tử nhỏ nhất và phần tử nhỏ nhì.

Lập trình C/C++

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

Trả lời Hủy