-3

サイズ L の部分配列の最小数。配列のすべての部分配列についてそれを見つける必要があります。すべてのサブアレイを個別にスキャンする以外に方法はありますか?

私は1つの解決策を念頭に置いています:

a[n]//the array
minimum[n-l+1]//the array to store the minimum numbers

minpos=position_minimum_in_subarray(a,0,l-1);
minimum[0]=a[minpos];
for(i=1;i<=n-l-1;i++)
{
    if(minpos=i-1)
    {
        minpos=position_minimum_in_subarray(a,i,i+l-1);
    }
    else {
        if(a[minpos]>a[i+l-1]) minpos=i+l-1;
        minimum=a[minpos];
    }
}

これよりも良い解決策はありますか?

4

3 に答える 3

2

両端キュー (Q) を使用できます。最小の要素が常に Q の先頭に表示され、Q のサイズが L を超えないようにする方法を見つけてください。したがって、一度ソリューションを作成すると、常に最大で要素を挿入および削除します。の上)。これはあなたを動かすための十分なヒントだと思います。

于 2012-09-08T09:37:58.677 に答える
1

あなたのソリューションは問題ないと思いますが、適切に機能するには次のようにする必要があります。

a[n]//the array
minimum[n-l+1]//fixed

minpos=position_minimum_in_subarray(a,0,l-1);
minimum[0]=a[minpos];
for(i=1;i<=n-l-1;i++)
{
    if(minpos=i-1)        
        minpos=position_minimum_in_subarray(a,i,i+l-1);                   
    else if(a[minpos]>a[i+l-1]) //fixed
        minpos=i+l-1; //fixed

    minimum[i] = a[minpos];
}

// Complexity Analysis :

//Time - O(n^2) in worse case(array is sorted) we will run
         "position_minimum_in_subarray" on each iteration

//Space - O(1) - "minimum array" is required for store the result

時間の複雑さを改善したい場合は、追加のスペースでそれを行うことができます。たとえば、各サブ配列を自己均衡 BST (赤黒木など) に格納し、反復ごとに最小値を取得できます。

for (int i= 0; i<n; i++) {
    bst.add(a[i]);

    if (bst.length == l) {
        minimum[i-l] = bst.min;
        bst.remove(a[i - l]);            
    }
  }

 //It's still not O(n) but close.

 //Complexity Analysis :

 //Time - O(n*log(l)) = O(n*log(n)) - insert/remove in self-balancing tree
                                      is proportional to the height of tree (log)

 //Space - O(l) = O(n) 
于 2012-09-08T09:50:29.523 に答える