6

私はspoj http://spoj.pl/problems/ARRAYSUBでこの問題を解決しようとしていました

2つのアプローチを使用して解決しました

まず、最適化されたブルート フォースを使用します。次に、k、2k、3k などでピボットを取り、最大値を見つけます。

最悪の場合、両方のソリューションが受け入れられますが、複雑さは O(n*k) です。

誰でも O(n) ソリューションを提案できますか 問題に対するアプローチ .

以下は、最悪のケースの複雑さ O(n*k) の私の Running Accepted コードです。

#include<iostream>
#include<cstdio>
#include<climits>
using namespace std;
main()
{
    long n;
    cin >> n;
    long *arr = new  long[n];
    for( long i=0;i<n;i++)
        cin >> arr[i];
     long k;
    cin >> k;
     long max=arr[0];
    for(long i=1;i<k;i++)
    {
        if(arr[i]>max)
            max=arr[i];
    }
    if(k!=n)
    cout<<max<<" ";
    else cout<<max;
    for( long i=k;i<n;i++)
    {
        if(arr[i-k]==max)
        {max=-1;
        for(int j=i-k+1;j<=i;j++)
        if(arr[j]>max)
        max=arr[j];
        if(i!=n)
        cout<<max<<" ";
        else cout<<max;

        }
        else{
        if(arr[i]>max)
        {   max=arr[i];

        if(i!=n)
        cout<<max<<" ";
        else 
        cout<<max;
        }
        else
        {
        if(i!=n)
        cout<<max<<" ";
        else cout<<max;}
        }
    }

        cout<<endl;
    return(0);
}
4

2 に答える 2

8

この問題を O(n) 時間で解決するために使用されるデータ構造は「deque」です。

ほとんどの人が考える自然な方法は、キューのサイズをウィンドウのサイズと同じに維持しようとすることです。この考えから抜け出し、既成概念にとらわれずに考えてみてください。冗長な要素を削除し、考慮する必要がある要素のみをキューに格納することが、以下の効率的な O(n) ソリューションを実現するための鍵です。

  void maxInWindow(vector<int> &A, int n, int k, vector<int> &B) {
  deque<int> Q;
  for (int i = 0; i < k; i++) {
    while (!Q.empty() && A[i] >= A[Q.back()])
      Q.pop_back();
    Q.push_back(i);
  }
  for (int i = k; i < n; i++) {
    B[i-k] = A[Q.front()];
    while (!Q.empty() && A[i] >= A[Q.back()])
      Q.pop_back();
    while (!Q.empty() && Q.front() <= i-k)
      Q.pop_front();
    Q.push_back(i);
  }
  B[n-k] = A[Q.front()];
  //B stores the maximum of every contiguous sub-array of size k    
}

説明 ：

最初の for ループは、最初の 'k' 要素の最大値を計算し、インデックスを Q.front() に格納します。これは B[0] = A[index] になります。次のセクションでは、A[i] が以前に格納された最大値よりも大きい場合に、後ろからプッシュ アンド ポップします。インデックスの値が ik よりも小さい場合は先頭からポップします。つまり、関連性がなくなったことを意味します。

于 2012-09-02T20:40:31.250 に答える
2

ブルート フォースよりも効率的なアプローチの 1 つは、データ構造として Red Black Trees (RB) を使用することです。RB ツリーには、O(log n) 時間で挿入、削除、最小値または最大値を見つけるというプロパティがあるためです。ここで、n はツリー内のノードの数です。

AVL ツリーにも同じプロパティがありますが、Big O の背後に隠されている定数は RB ツリーに比べて大きいです。

問題の全体的な複雑さは O(n lg k) になります。

最初に k 個のノードを RB ツリーに挿入し、find max を使用して最大要素を取得します。(2 * log k) 次に、挿入された最初の要素を削除し、新しい要素を挿入して、最大要素をクエリします。(3 * log k)。同じ手順に従って、およそ (3 * n * log k) が必要です。つまり、O(n* log k) です。

現在、単純なブルート フォース ソリューションは受け入れられていませんが、このソリューションは受け入れられています。

于 2014-01-18T13:25:14.903 に答える