C++에서 배열의 모든 요소에 대해 가장 가까운 큰 값 찾기

여기서 우리는 배열의 모든 요소에 대해 가장 가까운 큰 값을 찾는 방법을 볼 것입니다. 요소 x에 그보다 크고 배열에도 존재하는 다음 요소가 있는 경우 해당 요소의 더 큰 값이 됩니다. 요소가 없으면 -1을 반환합니다. 배열 요소가 [10, 5, 11, 6, 20, 12]이고 더 큰 요소가 [11, 6, 12, 10, -1, 20]이라고 가정합니다. 20은 배열에서 더 큰 값이 아니므로 -1을 인쇄합니다.

이를 해결하기 위해 C++ STL의 집합을 사용합니다. 이 집합은 이진 트리 접근 방식을 사용하여 구현됩니다. 이진 트리에서 항상 중위 계승자는 다음으로 큰 요소입니다. 따라서 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