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

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

เพื่อแก้ปัญหานี้ เราจะใช้การตั้งค่าใน C++ STL ชุด (Set) ถูกนำไปใช้โดยใช้วิธีต้นไม้ไบนารี ในต้นไม้ไบนารี ตัวถัดไปในลำดับ in-order จะเป็นองค์ประกอบที่มากกว่าถัดไป ดังนั้นเราสามารถรับองค์ประกอบได้ในเวลา 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