在 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, 6, 20, 12};
   int n = sizeof(arr) / sizeof(arr[0]);
   nearestGreatest(arr, n);
}

输出

11 6 12 10 -1 20

更新日期： 2019 年 11 月 1 日

333 次查看

启动你的职业

完成课程即可获得认证

开始
广告