如何回傳復雜度為O(n)的湍流序列？

#include <iostream>
#include <utility>

using namespace std;

pair<int,int> findLongestTurbulence(int arr[], int n){
    pair<int,int> ret  = {0,-1};
    int a = -1;
    for(int start = 0; start < n ; start   ){
        a = -1;
        for(int end = start 1; end < n ; end   ){
            if(a == -1){
                if(arr[end] > arr[end-1])
                    a=1;
                else if( arr[end] < arr[end-1])
                    a=0;
                else {
                    // no sequence can be generated starting with start 
                    if(end - start > ret.second - ret.first)
                        ret = {start,start};
                    break;      // CHECK FOR NEXT STARTING POINT
                }
            }
            else if(a == 0){
                if(arr[end] > arr[end-1]){
                    a = 1;
                }
                else{
                    // return this start and end point as this sequence cannot be extended more
                    if(end - start > ret.second - ret.first)
                        ret = { start, end-1};
                    break;
                }
            }
            else{
                if(arr[end] < arr[end-1]){
                    a = 0;
                }
                else{
                    // return this start and end point as this sequence cannot be extended more
                    if(end - start > ret.second - ret.first)
                        ret = { start, end-1};
                    break;
                }
            }
        }
    }
    
    return ret;
}
int main()
{
    int arr[] = {1,8,5,2,6,3,9,7,4,2,3}; // provided sequence 
    int n = sizeof(arr)/sizeof(arr[0]);
    pair<int,int> ans = findLongestTurbulence(arr,n);
    
    for(int i=ans.first;i<ans.second;i  ){
        cout<<arr[i]<<", ";
    }
    cout<<arr[ans.second]<<endl;
}

我的假設是它是 O(n^2) 因為它有兩個嵌套的 for 回圈。這段代碼試圖實作的目標是在序列中找到最長的湍流。“湍流”是一個連續的子序列，其中數字交替上升和下降。湍流的每個子序列也是湍流。例如，

? 1、8 和5 都是湍流，因為它們中的每一個都只包含一個數字。

? 1,8 和 8,5 都是湍流，因為 1 在第一個序列中上升到 8，而在第二個序列中 8 下降到 5。

? 1,8,5 是湍流，因為 1 上升到 8，然后下降到 5。

? 8,5,2 不是湍流，因為 8 下降了兩次（先下降到 5，然后下降到 2）。

? 給定序列中最長的湍流是5、2、6、3、9、7，這也是輸出。

我認為這個函式的時間復雜度是 O (n^2) 因為有兩個嵌套的 for 回圈。如何回傳復雜度為 O(n) 的湍流序列？

uj5u.com熱心網友回復：

我承認你的代碼對我來說太復雜了。我試過了，但我不明白。無論如何，它可以通過一個回圈來完成。為了簡單起見，我將使用兩個回圈（盡管不是嵌套的！）。一個回圈來查看 ifarr[i] < arr[i 1]或arr[i] > arr[i 1].

也保持簡單，您可以排除這種情況，arr[i] == arr[i 1]因為當陣列具有相等的后續元素時，您可以將演算法應用于子陣列。湍流從不包含元素arr[i] == arr[i 1]。

為了發明一些花哨的名字，我稱之為“極性” 1 when arr[i] > arr[i 1]and -1 when arr[i] < arr[i 1]at even i。在奇數索引處，極性反轉（即 -1 時arr[i] > arr[i 1]）。

這就是你會得到的：

#include <vector>
#include <iostream>
#include <iomanip>

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

    std::vector<int> polarity;
    int flip = 1;
    for (size_t i = 0; i < std::size(arr) -1;   i){
        if (arr[i] > arr[i 1]) polarity.push_back(1*flip);
        else polarity.push_back(-1*flip);
        flip *= -1;
    }
    for (size_t i = 0; i< std::size(arr);   i) {
        std::cout << std::setw(5) << arr[i] << " ";
    }
    std::cout << "\n";
    for (size_t i = 0; i < std::size(arr)-1;   i) {
        std::cout << std::setw(5) << polarity[i] << " ";
    }
}

輸出：

    1     8     5     2     6     3     9     7     4     2     3 
   -1    -1     1     1     1     1     1    -1     1     1 

我會留給你在polarity. 在這個例子中，它是1從元素開始的極性，值為5直到7（極性為 1 的最后一個條目對應于元素 9 和 7，這就是包含 7 的原因）。

標籤：C 算法 动态规划

上一篇：Docker容器不在windows上運行，埠不可用

下一篇：switch陳述句導致重復代碼