เราจะมาดูวิธีหาค่าที่ใกล้เคียงที่สุดสำหรับทุกองค์ประกอบในอาร์เรย์ หากองค์ประกอบ x มีองค์ประกอบถัดไปที่ใหญ่กว่า และยังมีอยู่ในอาร์เรย์ด้วย ค่านั้นจะมีค่ามากกว่าขององค์ประกอบนั้น หากไม่มีองค์ประกอบ ให้คืนค่า -1 สมมติว่าองค์ประกอบอาร์เรย์คือ [10, 5, 11, 6, 20, 12] ดังนั้นองค์ประกอบที่มากกว่าคือ [11, 6, 12, 10, -1, 20] เนื่องจาก 20 มีค่าไม่มากกว่าในอาร์เรย์ ให้พิมพ์ -1
เพื่อแก้ปัญหานี้ เราจะใช้ชุดใน C++ STL ชุดนี้มีการใช้งานโดยใช้วิธีการแบบไบนารีทรี ในไบนารีทรี ตัวตายตัวแทน inorder จะเป็นองค์ประกอบที่ใหญ่กว่าตัวถัดไปเสมอ เราจะได้องค์ประกอบในเวลา O(log 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, 6, 20, 12};
int n = sizeof(arr) / sizeof(arr[0]);
nearestGreatest(arr, n);
} ผลลัพธ์
11 6 12 10 -1 20
