Chương trình C++ tìm giá trị lớn hơn gần nhất cho mỗi phần tử mảng (phiên bản 2)

Tìm giá trị lớn hơn gần nhất cho mỗi phần tử mảng. Mảng [10,5,11,10,20,12] → [11,10,12,11,-1,20]. Phần tử 20 không có giá trị lớn hơn → -1.

Dùng set C++ STL (cây nhị phân). upper_bound trả về phần tử > key. O(log n) mỗi truy vấn.

Ví dụ mã nguồn

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

void nearestGreatest(int arr[], int n) {
    set<int> tempSet;
    for (int i = 0; i < n; i++)
        tempSet.insert(arr[i]);
    for (int i = 0; i < n; i++) {
        auto next_greater = tempSet.upper_bound(arr[i]);
        if (next_greater == tempSet.end())
            cout << -1 << " ";
        else
            cout << *next_greater << " ";
    }
}

int main() {
    int arr[] = {10, 5, 11, 10, 20, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    nearestGreatest(arr, n);
}

Kết quả đầu ra

11 10 12 11 -1 20