4

コーディング面接の質問です。配列が与えられ、swap 関数のみrandom_arrを使用して並べ替える必要があります。

また、各要素のスワップ数random_arrも制限されています。このparent_arrために、 の各要素のスワップ数を含む配列が与えられますrandom_arr。

制約:

  1. スワップ機能を使用する必要があります。
  2. 各要素は、最小 5 回、最大 26 回繰り返すことができます。
  3. 指定された配列の要素を 0 にすることはできません。
  4. ヘルパー関数を記述しないでください。

parent_arr宣言の仕方を説明します。次のような場合parent_arr：

parent_arr[] = {a,b,c,d,...,z} の場合

a can be swapped at most one time.

b can be swapped at most two times.

parent_arr[] = {c,b,a,....,z} の場合

c can be swapped at most one time.

b can be swapped at most two times.

a can be swapped at most three times

私の解決策：

random_arr[] の各要素について、ソートされている場合、その下にある要素の数を格納します。次に、parent_arr[] からスワップ カウントが最小の要素を選択し、random_arr[] に存在するかどうかを確認します。「はい」で、それが複数回発生している場合は、配置できる場所が複数あります。次に、最大のスワップカウントで位置（むしろその位置の要素、貴重な）を選択してスワップします。次に、その要素のスワップ カウントを減らし、parent_arr[] を並べ替えて、プロセスを繰り返します。

しかし、それは非常に非効率的であり、その正しさを証明することはできません. 何か案は？

4

1 に答える 1

4

まず、アルゴリズムを単純化しましょう。次に、その正しさを非公式に証明しましょう。

修正アルゴリズム

並べ替えられたシーケンスの各数値の下にある要素の数を計算すると、等しい要素xのグループごとに、並べ替えられた配列内での位置を決定するのに十分な情報が得られることに注意してください。たとえば、cが 7 回繰り返され、その前に 21 個の要素がある場合、cs が範囲を占めます[21..27](すべてのインデックスは 0 から始まります。範囲はその両端を含みます)。

parent_arrスワップの数が増える順に調べます。各要素についてx、そのターゲット範囲の開始を見つけますrb。また、そのターゲット範囲の終わりにも注意してくださいre。次に、範囲random_arr 外の要素を調べ[rb..re]ます。が表示されている場合はx、範囲に切り替えます。スワップ後、インクリメントしますrb。random_arr[rb]が に等しい場合は、xインクリメントを続けます。これらxの はすでに適切な場所にあるため、交換する必要はありません。

正しさの非公式証明

では、上記の正しさを証明しましょう。要素がその場所にスワップされると、再び移動されることはないことに注意してください。x内の要素に到達するparent_arrと、スワップ数が少ないすべての要素がすでに処理されています。アルゴリズムの構築により、これはこれらの要素が既に配置されていることを意味します。許可されたスワップの数があるとしxます。kその場所にスワップすると、別の要素が移動します。

ターゲット範囲内で宛先を検索するときにxアルゴリズムが s をスキップするため、この置換された要素を にすることはできません。さらに、置換された要素は の下の要素の 1 つになることはできません。これは、下のすべての要素が既にその場所にあるため、移動できないためです。これは、置換された要素のスワップ回数が必ず以上であることを意味します。処理を終了するまでに、すべての要素のほとんどのスワップを使い果たしているため (これは帰納法によって簡単に証明できます)、場所を空けるためにスワップ アウトする要素には、スワップを可能にするスワップが少なくとも 1 つ残っています。によって指示された順序で到達すると、所定の位置に配置されます。x[rb..re] xparent_arrxk+1xkxparent_arr

于 2013-02-06T19:08:22.793 に答える