1

整数要素の配列があるとしましょう。ここでは、重複する要素をすべて削除し、Java.util クラスを使用せずに残りの要素を出力したいと考えています。すべての重複をスキャンして削除するために2つのポインターを使用して解決しましたが、O(N ^ 2)かかります。このタスクを O(N) で完了できるアルゴリズムはありますか?

例：

Input Array:    [1, 2, 3, 4, 5, 4, 3, 4, 6]
Expected Array: [1, 2, 5, 6]
4

3 に答える 3

3

バケットを使用して O(N) + C (巨大な C) を達成できますが、ストレージが犠牲になります

  1. バケット[MAX_INT]と呼ばれるMAX_INTサイズのintの配列を作成します
  2. 入力配列をループします。値が x の場合、bucket[x]++ をインクリメントします。
  3. 入力配列を再度ループします。バケット[x] == 1の場合、すべてのxについて、予想される配列に追加します。

bucket[] 配列は、より優れたデータ構造に置き換えることができます。しかし、それでも O(N) を達成します

于 2013-11-04T06:49:46.113 に答える
1

セットを使用します。

for each item:
  if item is in the Set
    ignore it
  else
    copy it somewhere or output it or whatever
    add it to the Set

それはあなたのために働くはずです。

a を使用すると、 andHashSetに対して O(1) の複雑さがあるようです( Java でのセットの時間複雑さ)addcontains

于 2013-11-04T06:56:21.780 に答える