0

トップコーダーの問題ジグザグシーケンスを解決しようとしていました.私のコードの時間の複雑さはO（n * n）です。どうすれば O(n) または O(nlog (n)) に減らすことができますか? 疑似コードまたはアルゴリズムの説明は、私にとって非常に役立ちます。問題のステートメントは次のとおりです。問題文

連続する数の差が正と負の間で厳密に交互になる場合、数列はジグザグ数列と呼ばれます。最初の差異 (存在する場合) は、正または負のいずれかです。要素が 2 つ未満のシーケンスは、自明にジグザグ シーケンスです。

たとえば、1,7,4,9,2,5 は、差 (6,-3,5,-7,3) が交互に正と負になるため、ジグザグ シーケンスです。対照的に、1,4,7,2,5 と 1,7,4,5,5 はジグザグ シーケンスではありません。1 つ目は最初の 2 つの差が正であるため、2 つ目は最後の差がゼロであるためです。

整数のシーケンス sequence を指定すると、ジグザグ シーケンスであるシーケンスの最長のサブシーケンスの長さを返します。サブシーケンスは、元のシーケンスからいくつかの要素 (おそらくゼロ) を削除し、残りの要素を元の順序のままにすることによって取得されます。

そして、ここに私のコードがあります

#include <iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;

class ZigZag
{
  public:
  int dp[200][2];
  void print(int n)
  {
      for(int i=0;i<n;i++)
      {
          cout<<dp[i][0]<<endl;
      }
  }
  int longestZigZag(vector<int> a)
  {
      int n=a.size();
      //int dp[n][2];
      for(int i=0;i<n;i++)
      {
          cout<<a[i]<<" "<<"\t";
      }
      cout<<endl;
      memset(dp,sizeof(dp),0);
      dp[0][1]=dp[0][0]=1;
      for(int i=1;i<n;i++)
      {
            dp[i][1]=dp[i][0]=1;

            for(int j=0;j<i;j++)
            {
                if(a[i]<a[j])
                {
                   dp[i][0]=max(dp[j][1]+1,dp[i][0]);
                }
               if(a[j]<a[i])
               {
                    dp[i][1]=max(dp[j][0]+1,dp[i][1]);
               }
            }
            cout<<dp[i][1]<<"\t"<<dp[i][0]<<" "<<i<<endl;
            //print(n);
      }
      cout<<dp[n-1][0]<<endl;
      return max(dp[n-1][0],dp[n-1][1]);
  }
};
4

5 に答える 5

5

U は貪欲なアプローチを使用してO(n)でそれを行うことができます。繰り返しのない最初の数を取ります - これは、ジグザグ部分列の最初の数です。配列内の次の数値が最初の数値より小さいか大きいかを確認します。

ケース 1: lesserの場合、その次の要素をチェックし、最小の要素 (つまり、その後の要素が前の要素よりも大きい) が見つかるまで続けます。これが 2 番目の要素になります。

ケース 2:大きい場合、その次の要素をチェックし、最大の要素 (つまり、その後の要素が前の要素よりも小さい) が見つかるまで続けます。これが 2 番目の要素になります。

ケース 1 を使用して 2 番目の要素を見つけた場合は、ケース 2 を使用して 3 番目の要素を見つけます。元のシーケンスに要素がなくなるまで、これら 2 つのケースを交互に繰り返します。得られた結果の数値は、最長のジグザグ サブシーケンスを形成します。

例: { 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }

結果のサブシーケンス:

1 -> 1,17 (ケース 2) -> 1,17,5 (ケース 1) -> 1,17,5,15 (ケース 2) -> 1,17,5,15,5 (ケース 1) - > 1,17,5,15,5,16 (ケース 2) -> 1,17,5,15,5,16,8 (ケース 1)

したがって、最長のジグザグ サブシーケンスの長さは 7 です。

このアイデアの実装については、sjelkjd のソリューションを参照できます。

于 2012-10-23T11:41:48.340 に答える
1

サブシーケンスは必ずしも連続している必要はないため、O(n) にすることはできません。最悪の場合、複雑さは O(2^n) になります。ただし、できるだけ早くサブツリーを切断するためにいくつかのチェックを行いました。

int maxLenght;

void test(vector<int>& a, int sign, int last, int pos, int currentLenght) {
    if (maxLenght < currentLenght) maxLenght = currentLenght;
    if (pos >= a.size() || pos >= a.size() + currentLenght - maxLenght) return;
    if (last != a[pos] && (last - a[pos] >= 0) != sign) 
        test(a,!sign,a[pos],pos+1,currentLenght+1);
    test(a,sign,last,pos+1,currentLenght);
}

int longestZigZag(vector<int>& a) {
    maxLenght = 0;
    test(a,0,a[0],1,1);
    test(a,!0,a[0],1,1);
    return maxLenght;
}
于 2012-10-14T10:28:08.407 に答える
0

RMQを使用して、内側の for ループを削除できます。dp[i][0]との答えが見つかったら、dp[i][1]それを 2 つの RMQ ツリー (RMQ 0と RMQ 1dpなど) に保存します。これは、配列の 2 つの行で行っているのと同じです。したがって、 を計算するときdp[i][0]は、値をRMQ 0dp[i][0]の位置に置きます。これは、長さが徐々に番号 で終わるジグザグ シーケンスがあることを意味します。a[i]dp[i][0]a[i]

次に、 を計算するためにdp[i + 1][0]、0 から までのすべての数値をループする必要はありませんi。代わりに、位置 > の最大数についてRMQ 0をクエリできますa[i + 1]。これにより、現在の数値よりも大きい数値で終わる最長のジグザグ サブシーケンスが得られます。つまり、数値が減少するにつれて継続できる最長のシーケンスa[i + 1]です。次に、残りの半分のジグザグ サブシーケンスのRMQ 1に対して同じことを行うことができます。

のクエリ複雑度で動的 RMQ を実装できるためO(log N)、全体的な複雑度は になりO(N log N)ます。

于 2012-10-14T12:00:49.687 に答える
0

この問題は、O(n)時間とO(n)余分なスペースで解決できます。

アルゴリズムは次のようになります。

  1. 代替項の差を新しいサイズの配列に格納しますn-1
  2. 次に、新しい配列をトラバースして、代替項の積がゼロより小さいかどうかを確認します。
  3. それに応じて結果を増やします。トラバース中に配列の積が 0 より大きいことがわかった場合は、結果を格納し、差分配列の残りの要素のカウントを再度開始します。
  4. それらの中で最大のものを見つけて結果に保存し、return (result+1)

これがC++での実装です

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int> data(n);
    for(int i = 0; i < n; i++)
        cin>>data[i];
    vector<int> diff(n-1);
    for(int i = 1; i < n; i++)
        diff[i-1] = data[i]-data[i-1];
    int res = 1;
    if( n < 2)
        cout<<res<<"\n";
    else
    {
        int temp_idx = 0;
        for(int i = 1; i < n-1; i++)
        {
            if(diff[i]*diff[i-1] < 0)
            {
                temp_idx++;
                res++;
            }
            else
            {
                res = max(res,temp_idx);
                temp_idx = 1;
            }
        }
        cout<<res+1<<"\n";
    }
    return 0;
}
于 2014-11-06T08:26:19.593 に答える