5

配列 A = [5,1,7,2,3] を考えてみましょう

すべての連続部分配列 = { [5]、[1]、[7]、[2]、[3]、[5,1]、[1,7]、[7,2]、[2,3]、[ 5,1,7]、[1,7,2]、[7,2,3]、[5,1,7,2]、[1,7,2,3]、[5,1,7、 2,3] }

上記のセットのすべての配列をその中の最大要素に置き換えます。

セットは次のようになります: { [5], [1], [7], [2], [3], [5], [7], [7], [3], [7], [7] , [7], [7], [7], [7] }

頻度情報: [5] -> 2、[1] -> 1、[7] -> 9、[2] -> 1、[3] -> 2

私の目標は、上記の周波数情報を見つけることです。

私のアプローチ:

最初にペア (x,y) のリストを作成します。x は A の要素で、そのインデックスは y です。

リスト : [ (5,1), (1,2), (7,3), (2,4), (3,5) ]

最初の要素に関して降順でリストを並べ替えます。さて、

リスト : [ (7,3), (5,1), (3,5), (2,4), (1,2) ]

アルゴリズム：

def f( array, first_index, last_index):
       ->select an element from LIST starting from left which
         is not marked as visited and (first_index <= element.second <=   
         last_index)
       ->calculate frequency info of element in tuple as  (element.secondvalue-first_index+1) + (element.secondvalue-first_index+1)*(last_index - element.second_value)
       ->Mark above element as visited
       ->Recursively solve f( array, first_index,element.secondvalue-1 ),f( array,element.secondvalue+1,last_index)

適切なベースケースを簡単に設定できます。

時間計算量:O(n*n)

上記のアルゴリズムを使用するために多くのことを試みましたが、時間の複雑さを改善できませんでした。どうすれば改善できますか?ヒント、アプローチをいただければ幸いです。

4

4 に答える 4

1

値からインデックスへのマップを下から上にトラバースします。間隔の拡張ツリーを維持します。インデックスが追加されるたびに、適切な間隔を調整し、関連するセグメントから合計を計算します。

A = [5,1,7,2,3] => {1:1, 2:3, 3:4, 5:0, 7:2}

indexes     interval     total sub-arrays with maximum exactly
1           (1,1)        1 =>           1
1,3         (3,3)        2 =>           1 
1,3,4       (3,4)        3 =>           2
1,3,4,0     (0,1)        5 =>           2
1,3,4,0,2   (0,4)        7 => 3 + 2*3 = 9

拡張ツリーでの挿入と削除は、O(log n)時間の複雑さです。最悪の場合の合計時間の複雑さはO(n log n)です。

于 2015-08-11T01:36:27.203 に答える
1

あなたのコードが で実行されるとは思えませんO(n^2)。とにかく、これをより効率的な方法で解決する1つの方法は、各数値を、指定されたアイテムよりも小さい左/右のアイテムの数にマップすることです。例えば： 

input = [2 , 3 , 1 , 5 , 4 , 8 , 0]
for number n = 5
leftctsmaller(n) = 3
rightctsmaller(n) = 1

このマップO(n^2)を生成する必要があります。残りは簡単です。左右のスペースがあれば、それ自体nを除いてより小さい数値のみを含む部分配列の数を簡単に決定できnます。

于 2015-08-10T22:26:47.980 に答える
0

解決策を言葉で説明するのに苦労しています。コードを追加するだけです。それはそれ自体を説明します：

#include <iostream>
#include <fstream>
using namespace std;

#define max 10000

int main(int argc, const char * argv[]) {

    ifstream input("/Users/appleuser/Documents/Developer/xcode projects/SubArrayCount/SubArrayCount/input.in");

    int n, arr[max], before[max]={0}, after[max]={0}, result[max];
    input >> n;
    for (int i=0; i<n; i++)
        input >> arr[i];

    for (int i=0;i<n;i++)
        for (int j=i-1;j>=0&&arr[j]<arr[i];j-=before[j]+1)
            before[i]+=before[j]+1;

    for (int i=n-1;i>=0;i--)
        for (int j=i+1;j<n&&arr[j]<arr[i];j+=after[j]+1)
            after[i]+=after[j]+1;

    for (int i=0;i<n;i++)
        result[i]= (before[i]+1)*(after[i]+1);

    for (int i=0; i<n; i++)
        cout << result [i] << " ";
    cout << endl;

    return 0;
}

(before[i]+1)*(after[i]+1) の説明:

必要な値ごとに、数値は値の前と値未満にあり、数値は値の後にあり、値未満です。

  | 0  1  2  3  4  5 .... count of numbers less than the value and appears before.
---------------------
0 | 1  2  3  4  5  6
1 | 2  4  6  8  10 12
2 | 3  6  9  12 15 18
3 | 4  8  12 16 20 24
4 | 5  10 15 20 25 30
5 | 6  12 18 24 30 36
. | 
. |
. |
count of numbers less than the value and appears after.

例: それより 3 つ小さい値が前に表示され、それより 4 つ小さい値が後に表示される数値の場合。答えは V(3,4) = 20 = (3+1) * (4+1) です。

結果を教えてください。

于 2015-08-16T07:54:23.867 に答える