在C ++中查找数组中每个元素的最接近值

Z时代
2024-01-10
分类：综合

在这里，我们将看到如何为数组中的每个元素找到最接近的值。如果元素x的下一个元素大于它，并且也存在于数组中，则该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, 6, 20, 12};
   int n = sizeof(arr) / sizeof(arr[0]);
   nearestGreatest(arr, n);
}