โปรแกรม C++ หาค่าที่มากกว่าและใกล้ที่สุดสำหรับทุกสมาชิกในอาร์เรย์

ที่นี่เราจะดูวิธีหาค่าที่มากกว่าและใกล้ที่สุด (closest greater value) สำหรับทุกสมาชิกในอาร์เรย์ ถ้าสมาชิก x มีสมาชิกถัดไปที่มากกว่ามัน และอยู่ในอาร์เรย์ด้วย ค่านั้นจะเป็นค่าที่มากกว่าของสมาชิกนั้น ถ้าสมาชิกไม่มี ให้คืนค่า -1 สมมติสมาชิกอาร์เรย์คือ [10, 5, 11, 6, 20, 12] ค่าที่มากกว่าจะเป็น [11, 6, 12, 10, -1, 20] เนื่องจาก 20 ไม่มีค่ามากกว่าในอาร์เรย์ จึงพิมพ์ -1

เพื่อแก้ปัญหานี้ เราจะใช้ set ใน C++ STL set ถูกนำไปใช้ด้วยวิธีต้นไม้ไบนารี ในต้นไม้ไบนารี successor แบบ 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, 10, 20, 12}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    nearestGreatest(arr, n); 
}

ผลลัพธ์

11 10 12 11 -1 20