1

例如：

array[] = {3, 9, 10, **12**,1,4,**7**,2,**6**,***5***}

首先，我需要最大值=12，然后我需要数组其余部分中的最大值（1,4,7,2,6,5），所以值=7，然后数组其余部分的最大值为 6，然后是 5，之后，我将需要一系列这些值。这会返回 (12,7,6,5)。

如何获得这些数字？我已经尝试了以下代码，但它似乎是无限的我想我需要一个递归函数但我该怎么做呢？

max=0; max2=0;...
   for(i=0; i<array_length; i++){

             if (matrix[i] >= max)
                max=matrix[i];

             else {
                  for (j=i; j<array_length; j++){

                      if (matrix[j] >= max2)
                      max2=matrix[j];

                      else{
                       ...
                        ...for if else for if else
                         ...??
                      }
                  }
             }
         }
4

4 回答 4

5

这就是您在 C++11 中使用std::max_element()标准算法的方法：

#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    int arr[] = {3,5,4,12,1,4,7,2,6,5};

    auto m = std::begin(arr);
    while (m != std::end(arr))
    {
        m = std::max_element(m, std::end(arr));
        std::cout << *(m++) << std::endl;
    }
}

这是一个活生生的例子。

于 2013-05-08T20:34:05.613 回答
2

这是使用笛卡尔树数据结构的好地方。笛卡尔树是由具有以下属性的元素序列构建的数据结构：

  • 笛卡尔树是二叉树。
  • 笛卡尔树遵循堆属性：笛卡尔树中的每个节点都大于或等于它的所有后代。
  • 笛卡尔树的中序遍历返回原始序列。

例如，给定序列

4  1  0  3  2

笛卡尔树将是

   4
    \
     3
    / \
   1   2
    \
     0

请注意，这遵循堆属性，并且中序遍历返回序列4 1 0 3 2，这是原始序列。

但这里有一个关键的观察：注意如果你从这棵笛卡尔树的根开始向右走，你会得到数字 4（序列中最大的元素），然后是 3（接下来的最大元素）在 4 之后）和数字 2（在 3 之后的最大元素）。更一般地说，如果您为序列创建一个笛卡尔树，然后从根开始并继续向右走，您将得到您正在寻找的元素序列！

这样做的美妙之处在于，可以在时间 Θ(n) 内构建一棵笛卡尔树，这非常快，并且沿着脊柱走只需要 O(n) 时间。因此，找到您正在寻找的序列所需的总时间是 Θ(n)。注意“找到最大的元素，然后在之后出现的子数组中找到最大的元素，等等”的方法。如果输入按降序排序，则在最坏的情况下将在时间 Θ(n 2 ) 中运行，因此该解决方案要快得多。

希望这可以帮助！

于 2013-05-08T20:36:16.327 回答
0

如果您可以修改数组，您的代码将变得更简单。每当您找到一个最大值时，将其输出并将其在原始数组中的值更改为一些较小的数字，例如 -MAXINT。输出数组中元素的数量后，您可以停止迭代。

于 2013-05-08T20:33:36.470 回答
0 
std::vector<int> output;
for (auto i : array)
{
    auto pos = std::find_if(output.rbegin(), output.rend(), [i](int n) { return n > i; }).base();
    output.erase(pos,output.end());
    output.push_back(i);
}

希望您能理解该代码。我更擅长用 C++ 编写算法而不是用英语描述它们，但这里有一个尝试。

在我们开始扫描之前，output是空的。这是空输入的正确状态。

我们首先查看I输入数组中第一个未查看的元素。我们向后扫描输出，直到找到一个G大于的元素I。然后我们从 之后的位置开始擦除G。如果我们没有找到，这意味着它I是迄今为止我们搜索过的元素中最大的元素，所以我们删除了整个output. 否则，我们将删除 之后的每个元素G，因为I从G我们迄今为止搜索的内容开始，这是最棒的。然后我们追加I到output. 重复直到输入数组用完。

于 2013-05-08T22:22:55.593 回答