使用 C++ 替换每个元素为其右侧的最小更大元素

为了找到整数数组右侧的最小更大元素，我们需要考虑一个整数数组。对于每个元素，我们需要找到一个大于当前元素的元素，并且是在我们拥有的所有候选元素中最小的。假设我们有这样的元素：[5, 23, 65, 31, 76, 32, 87, 23, 76, 32, 88]。

vector<int> arr = {5,23,65,31,76,32,87,23,76,32,88};
solve(arr);

我们可以列出我们的需求，然后思考这些需求以找到解决方案。

我们需要一个数据结构 (ds) 来 -

  • 以排序顺序将元素添加到我们的 ds 中（每次我们将某些内容添加到我们的 ds 中时，都会有一个排序顺序）

  • 我们需要在我们的排序 ds 中进行 upper_bound 操作，以找到刚刚大于我们当前元素的元素，这将是答案，或者如果不存在这样的元素，则它将未定义。

我们将从右侧遍历元素。

根据需求，我们选择了集合 (set) 作为最佳数据结构。

为什么不是多重集合 (multiset)？我们没有任何存储重复元素的需求，所以我们不介意使用多重集合。

注意 - 您可能希望使用 2 个循环或二叉搜索树，但集合很好地满足了我们的需求，因此我们将在本文中使用集合。

示例

以下是替换数组中每个元素为其右侧最小更大元素的 C++ 实现 -

#include <iostream>
#include <set>
#include <vector>
using namespace std;
void solve (vector < int >&arr) {
   set < int >s;
   vector < int >ans (arr.size ());
   for (int i = arr.size () - 1; i >= 0; i--) {
      s.insert (arr[i]);
      auto it = s.upper_bound (arr[i]);
      if (it == s.end ())
         arr[i] = -1;
      else
         arr[i] = *it;
   }
}
void printArray (vector < int >&arr) {
   for (int i:arr)
      cout << i << " ";
   cout << "\n";
}
int main () {
   vector < int >arr = { 5, 23, 65, 31, 76, 32, 87, 23, 76, 32, 88 };
   printArray (arr);
   solve (arr);
   printArray (arr);
   return 0;
}

输出

5 23 65 31 76 32 87 23 76 32 88
23 31 76 32 87 76 88 32 88 88 -1

第 2 个元素 (23) 有一些候选元素 = [65, 31, 76, 32, 87, 76, 32, 88]，它们在 23 的右侧并且大于 23。现在我们需要从所有这些元素中选择最小值，它是 31，所以当前元素的答案变为 31。对于所有其他元素也是如此。所以元素变为

[23 31 76 32 87 76 88 32 88 88 -1]

结论

当我们将数组的每个元素存储到我们的集合中时，空间复杂度为 O(n)。我们的方法的时间复杂度为 O(n*log(n))，因为 upper_bound 和插入操作的成本为 log(n)，并且我们对每个元素都执行此操作。总体而言，这个问题纯粹是基于数据结构的。考虑到我们的需求，选择最佳数据结构是我们需要做的全部工作。

更新于: 2022 年 8 月 10 日

169 次浏览

开启您的 职业生涯

通过完成课程获得认证

立即开始
广告
© . All rights reserved.