各要素が2回出現する所与の配列内で最も長い距離の要素を見つけますか？

Question

intの配列が与えられた場合、各intは 配列に正確にTWICEと表示されます。このintのペアがこの配列の中で最大 の距離を持つようにintを見つけて返します。

[2, 1, 1, 3, 2, 3]

2: d = 5-1 = 4; 
1: d = 3-2 = 1; 
3: d = 6-4 = 2; 
return 2 

私のアイデア：

使用ハッシュマップ、キーがa[i]あり、その値はインデックスです。 a[]をスキャンし、各番号をハッシュに入れます。数値が2回ヒットした場合は、そのインデックスから古い数値インデックスを引いた値を使用し、その結果を使用してハッシュの要素値を更新します。

その後、ハッシュをスキャンして最大の要素（距離）のキーを返します。 時間と空間ではO（n）です。

O（n）時間とO（1）時間に行う方法は？

Answer 1

あなたは最大距離を持ちたいと思っていますので、検索する数字が最初と最後になる可能性が高いと思います。これは、配列の先頭から末尾まで同時にループする理由です。

[2, 1, 1, 3, 2, 3] 
Check if 2 == 3? 
Store a map of numbers and position: [2 => 1, 3 => 6] 
Check if 1 or 2 is in [2 => 1, 3 => 6] ? 

私は知っている、それは擬似コードではなく、完全ではなく、ただのアイデアを出すことです。

Answer 2

iLeftインデックスを最初の要素に設定し、iRightインデックスを2番目の要素に設定します。 左のアイテムのコピーを見つけるか、配列の最後を満たすまで、iRi​​ghtインデックスをインクリメントします。最初のケースで - 距離を覚えています。

iLeftをインクリメントします。新しいiRightから検索を開始する。 iRightの開始値は決して減少しません。 Delphiコード：

iLeft := 0; 
    iRight := 1; 

    while iRight < Len do begin //Len = array size 
    while (iRight < Len) and (A[iRight] <> A[iLeft]) do 
     Inc(iRight); //iRight++ 
    if iRight < Len then begin 
     BestNumber := A[iLeft]; 
     MaxDistance := iRight - iLeft; 
    end; 
    Inc(iLeft); //iLeft++ 
    iRight := iLeft + MaxDistance; 
    end; 

Answer 3

このアルゴリズムは、O（何らかの不正行為を伴う）（1）空間で、O（N）時間（平均）は、ソース・アレイは、非constする必要がある、最後にそれを破壊します。また、配列内の可能な値を制限します（各値の3ビットはアルゴリズム用に予約する必要があります）。

答えの半分は既に質問にあります。ハッシュマップを使用します。数値が2回ヒットした場合は、インデックスの差分を使用し、最適な結果を更新し、この数値をハッシュマップから削除して空き領域を確保します。 O（1）スペースにするには、ソース配列を再利用するだけです。配列をハッシュマップのインプレースに変換します。

配列要素をハッシュマップセルに変換する前に、その値と位置を覚えておいてください。この後、安全に上書きされる可能性があります。次に、この値を使用してハッシュマップ内の新しい位置を計算し、上書きします。要素は空のセルが見つかるまでこの方法でシャッフルされます。続行するには、まだ並べ替えられていない要素を選択します。すべてが再順序付けされると、すべてのintペアが確実に2回ヒットします。ここでは空のハッシュマップと更新された最良の結果値があります。

配列要素をハッシュマップセルに変換する際に予約ビットが1つ使用されます。最初はクリアされています。値がハッシュマップセルに並べ替えられると、このビットが設定されます。上書きされた要素にこのビットが設定されていない場合、この要素は次に処理されるために使用されます。このビットが上書きされる要素に設定されている場合は、ここで競合が発生しています（このビットが設定されていない最初の要素を選択して上書きします）。

2つ以上の予約ビットが競合する値を連鎖させるために使用されます。チェーンが開始/終了/継続する位置をエンコードします。

ハッシュマップセルには、3つの予約ビット、元の値インデックス、およびこの要素を一意に識別する情報が含まれている必要があります。これを可能にするために、ハッシュ関数は可逆でなければならず、テーブルの中の位置を考慮して値の一部を復元することができます。最も簡単なケースでは、ハッシュ関数はちょうどceil(log(n))最下位ビットです。表中の値は、3つのフィールドで構成さ：

32 - 3 - (ceil(log(n)))上位ビット元の値から

• 3予約ビット元の配列

時間複雑度の要素の位置について

ceil(log(n))ビットO（n）は平均してのみである。最悪の場合の複雑さはO（n^2）です。

このアルゴリズムの他の変形は、配列をハッシュマップに順次変換することです：各ステップで 2^mの最初の要素がハッシュマップに変換されています。 mが低い場合、パフォーマンスを向上させるために、一定のサイズの配列をハッシュマップとインターリーブすることができます。 mが高い場合は、すでに処理されている空間ペアが十分にあり、スペースは必要ありません。

Answer 4

O（n）時間とO（1）時間にこれを行う方法はありません。