-4

マイクロソフト インタビューの質問

HASHMAPとO（n）時間の複雑さを使用せずに、文字列から重複を削除します

O(n 2 ) 時間の複雑さで解決策がありますが、インタビューの質問では NO HASHMAP と O(n) 時間について具体的に言及しています。

並べ替えを使用し、O(n) スペースを使用する O(n log n) 時間よりも低い時間は考えられないため、任意のポインターを高く評価します。

4

3 に答える 3

11

一種のバケットソートを行います。

  • すべての単一文字を含む配列を作成します
  • 対応する文字のカウントを含む配列を作成します

このように 2 つの配列を使用している唯一の理由は、ハッシュ マップを明確に禁止したためです。この構造は自由に表現できます。char をints に変換できる場合は、配列を 1 つだけ使用する必要があります。

限られた数の可能な文字を想定しているため、各配列は一定のサイズ、またはO(1)になります。

  • 文字列を反復処理し、見つけたcountそれぞれに対してインクリメントします。カウントがすでに重複を見つけたcharよりも大きい場合。0

char 配列で特定の char を検索するにはO(1)時間がかかります。これは、char の数が限られているためです。

O(n)の正味実行時間に対して、この検索を n 回実行します。

配列がうまくいかない場合は、リンクされたリストを作成して、見つけた値のみを保持できます。リンクされたリストのサイズは依然として可能な文字数によって制限されているため、これは依然として一定です。

そのようにすれば、見た目がバケツソート戦略に似ていないことを除いて、ほぼ同じことを行うことになります。

于 2013-06-18T19:14:59.970 に答える
3

別の解決策があるかもしれませんが、それははるかに悪いと思いますが、小さな文字配列で機能します。アルゴリズムは次のとおりです。

  1. 各文字を 2 から始まる素数に割り当てます。 - これがルックアップ テーブルになります。
  2. すべての数の積を見つけます。-> O(n)
  3. ループ -> O(n) で、積 % k*k == 0 かどうかをチェックします。そうであれば、重複した k が見つかりました。

このソリューションは 1 つの数値のみを格納しますが、簡単にオーバーフローします。ただし、プライムテーブルは多くのスペースを必要とします。

編集: 40 の一意の文字しか使用できないという制約を追加すると、オイラーの二次多項式を使用して素数を見つけることができます。

P(n) = n*n − n + 41

これには、製品以外に追加のスペースは必要ありません。

于 2013-06-18T20:00:15.653 に答える
0 
traverse the list for i= 0 to n-1 elements
{
  check for sign of A[abs(A[i])] ;
  if positive then
     make it negative by   A[abs(A[i])]=-A[abs(A[i])];
  else  // i.e., A[abs(A[i])] is negative
     this   element (ith element of list) is a repetition
}

配列内の 0 に簡単に変更できます。文字の場合は、その整数コードを使用できます。

于 2013-06-19T05:01:01.230 に答える