2

助言？

並べ替えられていない配列と要素の数が与えられた場合、各要素について、数値-1がない場合は、それ自体と配列内で彼よりも小さい最も遠い要素との間の要素の数を出力する必要があります。

例：

入力：10 6 10 3 9 15出力：3 1 1 -1 -1 -1

私はすでにそれをしました、しかし私の教授はそれがはるかに効率的にすることができると言いました、もちろん私は実際にo（n ^ 2）をしています。分割統治？、二分探索？

私の解決策：

public void MedidaMolestia(int A[], int  N)
    {
    int i=0,  temp=0, k=N-1, j=0;

    for(i=0; i<N; i++) 
    {
        temp = A[i];

        for(j=N-1;j>i ; j--)
        {
            if(A[j]<temp)
            break;
        }

        if(i==j)
            System.out.print(-1 + " ");

        else 
            System.out.print((j-i)-1 + " ");
    }
}
4

1 に答える 1

0

ちょっとした動的プログラミングを使用して、漸近的な改善を提案できます。

  1. クイックソートを使用して、並べ替えられた配列の各要素のインデックスを取得します。O(n log n) を取ります。あなたの例では、次のようになります:-

    sindex = [3 1 3 0 5 2] ( since sorted array is 3 6 9 10 10 15)

  2. B[i] が i より小さいインデックスの右端から最初に出現するものを格納するように、配列 B を埋める必要があります。次のようにします:-

    Initialize B to [N, N,...]
filledpos = N;
for j = N-1 to 0 inclusive
    if(sindex[j] < filledpos) do 
    for i = sindex[j] to filledpos - 1 inclusive 
    // like if you find the 3rd smallest element fill B[4],.. B[filledpos]
       B[i] = j
    filledpos = sindex[j]

    あなたの例では、B = [2 2 3 3 5 5] です。O(n) の最悪のケースを取る

  3. これで、右端の要素 < i の位置がわかります。do the foll(takes O(n))

    for i = 0 to N-1
   print i - B[sindex[i]]
于 2012-12-03T21:43:49.103 に答える