10

これに対する解決策を見つけようとしましたが、あまり頭から抜け出すことができませんでした。

2 つのソートされていない整数配列 A と B が与えられます。配列 B が A の順列であるかどうかを確認する必要があります。これはどのように行うことができますか? 同じ XOR 値を持ついくつかの反例が存在する可能性があるため、数値を XOR しても機能しません。bt は互いに順列ではありません。

ソリューションは O(n) 時間で、スペース O(1) である必要があります

どんな助けでも大歓迎です!! ありがとう。

4

9 に答える 9

11

問題は理論的なものですが、O(n) 時間と o(1) 空間で実行できます。2 32 個のカウンターの配列を割り当て、それらをすべてゼロに設定します。配列のサイズが一定であるため、これは O(1) ステップです。次に、2 つの配列を反復処理します。配列 A については、読み取った整数に対応するカウンターをインクリメントします。配列 B については、デクリメントします。配列 B の反復中に負のカウンター値に遭遇した場合は、停止します --- 配列は互いの順列ではありません。それ以外の場合、最後に (前提条件として、A と B が同じサイズであると仮定します)、カウンター配列はすべてゼロであり、2 つの配列は互いの順列です。

これは、O(1) 空間と O(n) 時間のソリューションです。ただし、これは実用的ではありませんが、面接の質問に対する解決策として簡単に通用します。少なくともそうすべきです。

よりあいまいなソリューション

  • 非決定論的計算モデルを使用して、2 つの配列が互いの順列ではないことを確認することは、2 つの配列で異なるカウントを持つ要素を推測することにより、O(1) 空間、O(n) 時間で実行できます。両方の配列のその要素のインスタンス。

  • 計算のランダム化モデルでは、ランダム交換ハッシュ関数を構築し、2 つの配列のハッシュ値を計算します。ハッシュ値が異なる場合、配列は互いの順列ではありません。そうでなければ、そうかもしれません。何度も繰り返して、エラーの確率を目的のしきい値より低くします。また、O(1) 空間で O(n) 時間のアプローチですが、ランダム化されています。

  • 並列計算モデルでは、'n' を入力配列のサイズとします。「n」個のスレッドを割り当てます。すべてのスレッド i = 1 .. n は、最初の配列から i 番目の数値を読み取ります。それを×とする。次に、同じスレッドが最初の配列で x の出現回数をカウントし、2 番目の配列で同じカウントをチェックします。すべての単一スレッドは、O(1) スペースと O(n) 時間を使用します。

  • 整数配列 [ a1, ..., an ] を多項式 x a1 + x a2 + ... + x anとして解釈します。ここで、x は自由変数であり、得られた 2 つの多項式の等価性を数値的にチェックします。O(1) 空間と O(n) 時間演算には浮動小数点演算を使用します。丸め誤差と等価性の数値チェックが確率的であるため、正確な方法ではありません。あるいは、素数を法とする整数の多項式を解釈し、同じ確率的チェックを実行します。

于 2012-05-17T16:52:50.273 に答える
7

素数の大きなリストに自由にアクセスできる場合は、素因数分解のプロパティを利用してこの問題を解決できます。

両方の配列について、各整数 i について Prime[i] の積を計算します。ここで、Prime[i] は i 番目の素数です。配列の積の値は、それらが互いの順列である場合に等しくなります。

ここで素因数分解が役立つ理由は 2 つあります。

  1. 乗算は推移的であるため、積を計算するためのオペランドの順序は関係ありません。(配列がソートされていれば、この問題は些細なことだという事実をほのめかした人もいます。乗算することで、暗黙的にソートしています。)
  2. 素数は無損失で乗算されます。ある数値を与えられ、それが素数のみの積であると伝えられた場合、どの素数がどの素数に入力されたかを正確に計算できます。

例：

a = 1,1,3,4
b = 4,1,3,1
Product of ith primes in a = 2 * 2 * 5 * 7 = 140
Product of ith primes in b = 7 * 2 * 5 * 2 = 140

そうは言っても、おそらく素数のリストへのアクセスは許可されていませんが、そうでなければこれは良い解決策のように思われるので、投稿したいと思いました.

于 2012-05-20T04:08:31.060 に答える
5

これは実際にはantti.huimaの回答に対するコメントである必要があるため、回答として投稿して申し訳ありませんが、コメントする評判はまだありません。

カウンター配列のサイズは、入力配列内の特定の値のインスタンス数に依存するため、O(log(n)) のようです。

たとえば、入力配列 A がすべて 1 で、長さが (2^32) + 1 であるとします。これには、エンコードするためにサイズ 33 ビットのカウンターが必要になります (実際には、配列のサイズが 2 倍になりますが、理論にとどまる）。A のサイズを 2 倍にすると (すべて 1 の値のまま)、各カウンターに 65 ビットが必要になります。

これは非常に細かい議論ですが、これらのインタビューの質問は非常に細かい傾向があります.

于 2012-05-18T15:50:47.117 に答える
3

これをその場でソートする必要がない場合は、次のアプローチが機能する可能性があります。

  1. HashMap を作成し、Key を配列要素、Value を出現回数とします。(同じ番号の複数回の発生を処理するため)
  2. 配列 A をトラバースします。
  3. HashMap に配列要素を挿入します。
  4. 次に、配列 B をトラバースします。
  5. HashMap で B のすべての要素を検索します。対応する値が 1 の場合、エントリを削除します。それ以外の場合は、値を 1 減らします。
  6. 配列 B 全体を処理でき、その時点で HashMap が空であれば、成功です。そうでなければ失敗。

HashMap は一定のスペースを使用し、各配列を 1 回だけトラバースします。

これがあなたが探しているものかどうかわかりません。空間/時間に関する制約を逃した場合はお知らせください。

于 2012-05-20T22:39:22.800 に答える
1

計算 O(n) という 2 つの制約が与えられます。ここで、n は A と B の両方とメモリ O(1) の合計の長さを意味します。

2 つの系列 A、B が互いの順列である場合、A または B のいずれかの順列から生じる系列 C も存在します。したがって、問題は、A と B の両方を系列 C_A と C_B に順列し、それらを比較することです。

そのような順列の 1 つが並べ替えです。その場で機能するいくつかの並べ替えアルゴリズムがあるため、A と B をその場で並べ替えることができます。最良のシナリオでは、Smooth Sort は O(n) の計算量と O(1) のメモリの複雑さで並べ替え、最悪の場合は O(n log n) / O(1) になります。

要素ごとの比較は O(n) で行われますが、O 表記では O(2*n) = O(n) であるため、Smooth Sort と比較を使用すると、O(n) / O(1) チェックが行われます。 2 つのシリーズは互いの順列です。ただし、最悪の場合は O(n log n)/O(1) になります

于 2012-05-20T22:53:28.010 に答える
1

解は O(n) 時間で、スペースは O(1) である必要があります。これはソートを省略し、スペース O(1) の要件は、おそらく文字列のハッシュを作成してそれらを比較する必要があるというヒントです。

素数リストにアクセスできる場合は、cheeken のソリューションに従ってください。

注: 素数リストにアクセスできないと面接官が言った場合。次に、素数を生成して保存します。アルファベットの長さが定数であるため、これは O(1) です。

それ以外の場合は、私の別のアイデアです。簡単にするために、アルファベットを = {a,b,c,d,e} と定義します。文字の値は次のように定義されます。

a, b, c, d, e
1, 2, 4, 8, 16

注: インタビュアーがこれは許可されていないと言った場合は、アルファベットのルックアップ テーブルを作成します。アルファベットのサイズは一定であるため、これには O(1) スペースが必要です。

文字列内の個別の文字を見つけることができる関数を定義します。

// set bit value of char c in variable i and return result
distinct(char c, int i) : int

E.g. distinct('a', 0) returns 1
E.g. distinct('a', 1) returns 1
E.g. distinct('b', 1) returns 3

したがって、文字列「aab」を反復すると、distinct 関数は結果として 3 を返すはずです

文字列内の文字の合計を計算できる関数を定義します。

// return sum of c and i
sum(char c, int i) : int

E.g. sum('a', 0) returns 1
E.g. sum('a', 1) returns 2
E.g. sum('b', 2) returns 4

したがって、文字列「aab」を反復すると、sum 関数は結果として 4 を与えるはずです。

文字列の文字の長さを計算できる関数を定義します。

// return length of string s
length(string s) : int

E.g. length("aab") returns 3

2 つの文字列に対してメソッドを実行し、結果を比較すると、O(n) の実行時間がかかります。ハッシュ値を格納するには、O(1) のスペースが必要です。

 e.g. 
 distinct of "aab" => 3
 distinct of "aba" => 3
 sum of "aab => 4
 sum of "aba => 4
 length of "aab => 3
 length of "aba => 3

両方の文字列のすべての値が等しいため、それらは互いの順列である必要があります。

編集：コメントで指摘されているように、特定のアルファベット値では解決策が正しくありません。

于 2012-05-28T14:32:05.130 に答える
0

2 つの配列のいずれかをインプレース ハッシュテーブルに変換できます。これは正確には O(N) ではありませんが、非病的なケースではそれに近づきます。

[number % N] を目的のインデックスとして、またはそこから始まるチェーンで使用するだけです。要素を置き換える必要がある場合は、問題のある要素が開始されたインデックスに配置できます。すすぎ、洗い、繰り返し。

更新: これは同様の (N=M) ハッシュ テーブルです。チェーンを使用していましたが、オープン アドレッシングにダウングレードできます。

于 2012-05-17T16:53:09.110 に答える
0

エラーの可能性が低いランダム化されたアルゴリズムを使用します。

重要なのは、ユニバーサル ハッシュ関数を使用することです。

def hash(array, hash_fn):
  cur = 0
  for item in array:
    cur ^= hash_item(item)
  return cur

def are_perm(a1, a2):
  hash_fn = pick_random_universal_hash_func()
  return hash_fn(a1, hash_fn) == hash_fn(a2, hash_fn)

配列が順列である場合、それは常に正しいでしょう。それらが異なる場合、アルゴリズムはそれらが同じであると誤って言う可能性がありますが、非常に低い確率でそうします。さらに、同じ入力に対して多くの are_perm() 質問をすることで、直線的な量の作業でエラーの可能性を指数関数的に減少させることができます。

于 2012-05-17T18:20:24.450 に答える
0

反例を見つけただけです。したがって、以下の仮定は正しくありません。

私はそれを証明することはできませんが、これは真実である可能性があると思います.

配列のすべての要素は整数であるため、各配列に 2 つの要素があるとします。

a1 + a2 = s
a1 * a2 = m

b1 + b2 = s
b1 * b2 = m

then {a1, a2} == {b1, b2}

これが true の場合、配列が n 個の要素を持つ場合は true です。

したがって、各配列の合計と積を比較し、それらが等しい場合、一方は他方の順列です。

于 2012-05-18T16:01:50.380 に答える