4

これはインタビューの質問です (フォーラムで見ましたが、最善の解決策を見つけることができません)。問題は、与えられた一連の数値から最短経路を見つけることです。

例えば。

Set A - [2, 14, 34]
Set B - [9, 13]
Set C - [15, 22, 62, 78]
Set D - [16, 24, 54]
Set Z - [17, 38, 41]

1) セット数はいくつでも構いません

2) セット内の数字は決して繰り返されません。

3) 番号は任意の開始点から任意の終了点までの範囲で指定できます (0 から n の間ではありません。つまり、1091 から 1890 までの範囲で開始できます)。

4) すべてのセットがソートされます。

上記の例では、パスは次のようになります。

B[13] -> A[14] -> C[15] -> D[16] -> Z[17]

最短経路は、最大数 (17) - 最小数 (13) = 4 の差として定義されます。

何か案は ？

4

5 に答える 5

3

ペア [number, name_of_set] のリストを作成します。並べ替えます。

指定された長さのパス D について、2 つのポインターを保持しながら、並べ替えられたリストをスキャンします。常に最初のポインターを増やし、拡散が D より大きい間は 2 番目のポインターを増やします。スキャン中は、各セットに属するポインター間の要素のカウントを保持します。各セットの要素があれば、ビンゴ、差が最大で D のパスを見つけました。

次に、D の二分探索を行います。

全体的な複雑さ O(N log N)

于 2012-07-27T12:30:06.887 に答える
1

ヒープ (プライオリティ キュー) が役立つ場合があります。

  1. すべてのデータを配列 N に並べ替え、元のセット ID も保持します。合計で m 個のセットがあると仮定します。
  2. int shortest = MAX(N) - MIN(N); // つまり N[N.length - 1] - N[0]
  3. ヒープ h を初期化します。
  4. i を使用して N をループします。h に N[i] と同じセットの要素が含まれていない場合は、N[i] をヒープに追加します。h に同じセットの要素が既に含まれている場合 (h[k] など)、h[k] のキーを N[i] に増やします。h.size() == m の場合、最短 == N[i] - h[0] < 最短 ? N[i] - h[0]: 最短。

コードは次のとおりです。

mergesort(all_sets[], H, S); // H holds all data, S holds corresponding setid.
Heap<key, setid> H = new Heap<key, setid>();
int shortest = N[N.length - 1] - n[0];
for(int i = 0; i < N.length; i++)
{
   int data = N[i];
   int setID = S[i];
   int hindex = H.elementFromSet(setID);
   if(hindex < 0)
    { // H does not have any element from set with setID;
       H.add(data, setID);
    } else {
       H.increase(data, hindex);
    }
    if(H.size() == m)
    {
       shortest = shortest > N[i] - H[0]? N[i] - H[0] : shortest;
    }
}

ハッシュテーブルを使用して、セット ID をヒープ インデックスに追跡し続けることができるかもしれません。

私が信じるランタイムはO(nlgm)です。

于 2012-07-29T06:59:50.753 に答える
0

この質問で説明したアルゴリズムと本質的に同じ考え方を適用できます。

最終サブセットの中心を探しましょう。各セットへの最大距離を最小限に抑える必要があります。いつものように、ポイントからセットまでの距離は、ポイントとセットの要素の間の最小距離として定義されます。

各セットについて、セットまでの距離を表すi関数は区分線形です。fia,b が 2 つの連続する数である場合、この関係により、線形時間内fi(a) = 0, fi((a+b)/2) = (b-a)/2, fi(b) = 0のすべての記述を作成できます。fi

fiしかし、2 つの区分関数の最大値を線形時間で計算することもできますfj。これらが線形である連続した間隔 [a,b] を考慮することにより、結果が線形であるか、または機能をパーティションに追加します。関数の勾配は常に +1 または -1 であるため、交点は半整数であり、浮動小数点 (または固定小数点) 演算で正確に表すことができます。

凸性引数はg、すべての最大値が最大で のfi2 倍のポイントしか持てないことを示しているfiため、最大値がセット数で指数関数的になるポイント数を持つことを心配する必要はありません。

だから私たちはただ：

  1. fiの区分線形距離関数を計算しi = 1..pます。
  2. 最大値を繰り返し計算してg、すべての最大値を計算します。fi
  3. の任意の最小点の位置がg目的の中心です。
  4. セットごとに、中心に最も近いポイントを選択します。
  5. 選択したポイントのセットの幅は、正確にg:-)の最小値です。

セットの数が制限されている場合、複雑さは O( N ) であり、セットの数pが可変の場合は O( N p )です。最大値の計算方法 (分割統治) を賢くすることで、それを O( N log p ) に減らすこともできると思います。

于 2012-07-27T13:07:25.120 に答える
0

  1. セット A とセット B を取ります。このセットで最短経路を見つけます。これは 14-13 になります。13 ～ 14 になるように並べ替えます。ここで、ショート セット short = {13,14}

  2. ショート セット { 13, 14} を取り、セット C {15,22,62,78}. ここで、ショート セットの開始ノードは 13 で、終了ノードは 14 です。エンド ノード 14 から開始して、到達可能な最短パスは 15 です。したがって、15 を短いセットに追加します。ショート セットは {13, 14 , 15} になり、{13, 14, 15} のままになるように並べ替えます

  3. ここで、短い集合 {13,14,15} と集合 D { 16 , 24 , 54} を取ります。短い集合の終了ノードは 15 です。そこで、そこから始めます。25 からセット D への最短経路は 16 です。したがって、短いセットに 16 を追加します。ショート セットは { 13,14,15,16} になります。並べ替えます。{13,14,15,16}のままです

3. セット全体に対してこれを繰り返して、結果の短いセットを取得できます。

于 2012-07-27T11:11:42.623 に答える
0

これは、問題の別の定式化です。

Q: すべてのセットから要素を含む最小の区間を見つけます。

A:

  1. すべての要素を 1 つのバケットに入れて並べ替えます。複雑さ O(N*K)
  2. 二分探索によって、この数値よりも高い各セットから少なくとも 1 つの要素が存在するような最大の数値を見つけます。これは MIN になります。
  3. 同様に、二分探索によって、この数よりも小さい要素が各セットから少なくとも 1 つ存在するような最小の数を見つけます。これがMAXになります。

最適化として、各セットを間隔として保存し、ステップ 2 と 3 のクエリに間隔ツリーを使用できます。これにより、クエリの複雑さが O(K) から O(log K) に変わります。

于 2012-07-28T14:23:22.110 に答える