2

3 つの並べ替えられた配列 (昇順) が与えられ、距離が最小になるようにトリプレット (各配列から 1 つの要素) を見つける必要があります。距離は次のように定義されます。a[i], b[j]とc[k]が 3 つの要素の場合

distance = max{abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k])}

O(n)時間の複雑さで解を与えてください

4

2 に答える 2

4

線形時間アルゴリズム:

double MinimalDistance(double[] A, double[] B, double[] C)
{
    int i,j,k = 0;
    double min_value = infinity;
    double current_val;
    int opt_indexes[3] = {0, 0, 0);

    while(i < A.size || j < B.size || k < C.size)
    {
         current_val = calculate_distance(A[i],B[j],C[k]);
         if(current_val < min_value)
         {
               min_value = current_val;
               opt_indexes[1] = i;
               opt_indexes[2] = j;
               opt_indexes[3] = k;
         }    

         if(A[i] < B[j] && A[i] < C[k] && i < A.size)
             i++;
         else if (B[j] < C[k] && j < B.size)
             j++;
         else
             k++; 
    }

    return min_value;
}

各ステップで現在の距離を確認し、現在指している配列のインデックスを最小値に増やします。各配列は正確に 1 回繰り返されます。つまり、実行時間はO(A.size + B.size + C.size)です。

最小値ではなく最適なインデックスが必要な場合は、opt_indexes代わりにを返すことができますmin_value。

于 2013-10-18T12:42:34.087 に答える
1

並べ替えられた配列が 1 つしかない場合、可能な距離が少ない 3 つの連続した要素が望ましいソリューションであるとします。3 つの配列がある場合は、それらをすべてマージして大きなソート済み配列 ABC を作成し (これはマージソートのマージ操作によって O(n) で実行できます)、どの要素がどの元の配列に属しているかを判断するフラグを保持するだけです。 . 次のように、配列内の 3 つの連続する要素を見つける必要があります。

a1,a2,b1,b2,b3,c1,b4,c2,c3,c4,b5,b6,a3,a4,a5,....

ここで連続とは、連続した順序で 3 つの異なるグループに属していることを意味します。たとえば、a2、b3、c1 または c4、b6、a3 です。

このツリー要素を見つけることは難しくありません。最小と最大のものは、いくつかのトリプルの最初と最後のグループの要素の最後と最初にある必要があります。たとえば、[c2、c3、c4]、[b5、b6]、 [a3,a4,a5]、a4,a5,c2,c3この場合の可能な解が c4、[b5、b6]、a5 の中にあることを確認する必要はありません。また、c4 を b5、b6 と比較する必要もありません。 a5 with b5,b6, 確かに距離は a5-c4 (このグループ内) によって作られています. したがって、左から開始して最後の要素を追跡し、各グループの最後にアクセスした値を保持するだけで、各反復で可能な最善のソリューションを更新できます。

例（これは私ではなくOPの仕事だと思うので、最初に私はコードを書いていないと言わなければなりません）：

並べ替えられた配列の後に次のシーケンスがあるとします。

a1,a2,b1,b2,b3,c1,b4,c2,c3,c4,b5,b6,a3,a4,a5,....

ステップごとに繰り返します：

配列の各項目の最後の項目を追跡する必要があるだけです。aこれは、現在の最良の a_i、b_i の b、および c_i の c を追跡するためです。最初に a_i=b_i=c_i=-1 とします。

最初のステップで a は a1 になり、次のステップで

a=a2,b=-1,c=-1
a=a2,b=b1,c=-1
a=a2,b=b2,c=-1
a=a2,b=b3,c=-1,
a=a2,b=b3,c=c1,

この時点で、現在のポインター (a2、b3、c1) を差分の最適値として保存します。

次のステップでは:

a=a2,c=c1,b=b4

ここで、b4-a2 の違いを以前の最良のオプションと比較します。より優れている場合は、このポインターを現在までのソリューションとして保存し、次に進みます。

a=a2,b=b4,c=c2 (again compare and if needed update the best solution),
a=a2,b=b4,c=c3 (again ....)
a=a2,b=b4,c=c4 (again ....)
a=a2, b=b5,c=c4, ....

テキストから明確でない場合は、マージ後に次のようになります (すべての配列に少なくとも 1 つの要素があると仮定します)。

解決策 = 無限; a=b=c=-1, ベストA=ベストB=ベストC=1;

for (int i=0;i<ABC.Length;i++)
{
    if(ABC[i].type == "a") // type is a flag determines 
                           // who is the owner of this element
    {
        a=ABC[i].Value; 
        if (b!=-1&&c!=-1)
        {
          if (max(|a-b|,|b-c|,|a-c|) < solution)
          {
            solution =  max(|a-b|,|b-c|,|a-c|);
            bestA= a,bestB = b,bestC = c;
          }
        }
    }
    // and two more if for type "b" and "c"
}

確かにこれよりも洗練されたアルゴリズムがありますが、あなたのリンクに問題があったようです。問題を簡単に見るこの簡単な方法で、後で自分のリンクを理解できるようになると思います。

于 2013-10-18T12:43:30.877 に答える