資料結構
網路
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 次瀏覽
廣告