数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律学在 C++ 中为数组中的每个元素查找最临近的较大值
我们将在本文中了解如何为数组中的每个元素查找最临近的较大值。如果一个元素 x 具有比它大的且同时存在于数组中的下一个元素，那么其便是该元素的较大值。如果该元素不存在，则返回 -1。假设数组元素为 [10, 5, 11, 6, 20, 12]，则较大元素为 [11, 6, 12, 10, -1, 20]。由于 20 在数组中没有较大值，因此输出 -1。
为了解决这个问题，我们将利用 C++ STL 中的 set。该集合是使用二叉树方法实现的。在二叉树中，中序后继始终是下一个较大元素。因此，我们可以在 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
更新于： 2019 年 11 月 1 日
262 次浏览
广告