查找陣列

Question

的休止符的最大值例如：

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

首先，需要最大值= 12然後我需要陣列的其餘部分之間的最大值（1,4,7,2,6,5 ），所以value = 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 
         ...?? 
         } 
        } 
      } 
     } 

Answer 1

這是你會怎麼做，在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; 
    } 
} 

這裏是一個live example。

Answer 2

如果你可以修改數組，你的代碼會變得更簡單。無論何時找到最大值，輸出並將原始數組內的值更改爲某個小數值，例如-MAXINT。一旦輸出了數組中的元素數量，就可以停止迭代。

Answer 3

這是一個很好的使用Cartesian tree數據結構的地方。笛卡爾樹是由具有以下屬性的元素序列構建的數據結構：

• 笛卡爾樹是一棵二叉樹。
• 笛卡爾樹服從heap屬性：笛卡爾樹中的每個節點都大於或等於它的所有後代。
• 笛卡爾樹的一個序列遍歷給出了原始序列。

例如，給定的順序

4 1 0 3 2 

笛卡爾樹將

4 
    \ 
    3 
    /\ 
    1 2 
    \ 
    0 

注意，這遵循了堆屬性，和中序步行還給序列4 1 0 3 2，這是原始序列。

但是，這裏有一個關鍵的觀察：注意，如果你從這個笛卡爾樹的根部開始走到右邊，你會得到數字4（序列中最大的元素），然後是3（最大元素之後是什麼4）和數字2（3之後的最大元素）。更一般地說，如果你爲序列創建了一個笛卡爾樹，那麼從根開始並繼續向右走，你會找回你正在尋找的元素序列！

美麗的是，笛卡爾樹可以是constructed in time Θ(n)，這是非常快的，走下脊柱只需要時間O（n）。因此，查找您要查找的序列所需的總時間爲Θ（n）。請注意，「找到最大的元素，然後找到在其後出現的子數組中最大的元素等」的方法。在最壞的情況下，如果輸入按降序排序，則會在時間上運行Θ（n ），所以該解決方案要快得多。

希望這會有所幫助！

Answer 4

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。重複，直到輸入數組耗盡。