Ở đây chúng ta sẽ xem cách tìm giá trị lớn hơn gần nhất cho mọi phần tử trong một mảng. Nếu một phần tử x có phần tử tiếp theo lớn hơn nó và cũng có mặt trong mảng, thì đó sẽ là giá trị lớn hơn của phần tử đó. Nếu phần tử không có mặt, thì trả về -1. Giả sử các phần tử của mảng là [10, 5, 11, 6, 20, 12], thì các phần tử lớn hơn là [11, 6, 12, 10, -1, 20]. Vì 20 không có giá trị lớn hơn trong mảng, sau đó in -1.
Để giải quyết điều này, chúng tôi sẽ sử dụng tập hợp trong C ++ STL. Tập hợp được thực hiện bằng cách tiếp cận cây nhị phân. Trong cây nhị phân luôn luôn có phần tử kế tiếp nhỏ hơn là phần tử lớn hơn tiếp theo. Vì vậy, chúng ta có thể lấy phần tử trong thời gian O (log n).
Ví dụ
#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);
} Đầu ra
11 10 12 11 -1 20