Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

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


เราจะมาดูวิธีหาค่าที่ใกล้เคียงที่สุดสำหรับทุกองค์ประกอบในอาร์เรย์ หากองค์ประกอบ 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