1

重複を検索し、重複インデックスを別の配列に格納するメソッドを作成しました。次に、大きな配列を実行し、すべてのエントリを重複せずに移動します。

さて、私の問題は、これがO（N * N）を使用し、配列を追加しているため、追加のメモリスペースを使用していることです。

これはどのように行うことができますか？追加のライブラリやHashSetを使用せずにこれを行う方法を理解する必要があると仮定します。

ヒントをいただければ幸いです。

   public void dups()
   {
       int[] index = new int[100];

       int k = 0;
       int n = 0;
       int p = 0;

       for (int i = 0; i < elements; i++)
           for (int j = i + 1; j < elements; j++)
               if(a[j].equals(a[i]))
                   index[k++] = i;

       for (int m = 0; m < elements; m++)
           if (m != index[p])
               a[n++] = (T) a[m];
           else
               p++;

       elements -= k;
   }
4

4 に答える 4

4

O(n)（一般的に）で重複を見つけることはできません。

ただし、で可能ですO(n*log n)。配列（O(n*log n)）を並べ替えるだけで、で重複のスキャンを実行できますO(n)。

一方、ハッシュテーブルを使用できる場合（追加のライブラリを使用したくない場合は、おそらく実行したくないこと）、配列をスキャンして、各要素が配列に表示される頻度をカウントできます。 。その後、ハッシュテーブルの各要素を調べて、複数回出現した要素を見つけることができます。これには、予想される実行時間がかかりますがO(n)、決定論的ではありませんO(n)。

O(n)最後に、なぜ私はあなたが一般的に重複を見つけることができないと書いたのですか？
で重複を見つけることが可能ないくつかの特殊なケースを想像することができO(n)ます。たとえば、配列に含めることができるのは0〜99の数値のみです。その場合、別の配列（サイズ100）を使用して、各要素が配列に表示される頻度をカウントできます。これはハッシュテーブルの場合と同じように機能しますが、その実行時間は決定論的O(n)です。

重複を見つけることが可能な別の例O(n)は、もちろん、配列がすでにソートされている場合です。

于 2012-10-09T18:35:57.053 に答える
1

HashSetこれをO（n）時間で行うには、aを使用します。

public <T> int removeDups(T[] original) {
    HashSet<T> unique = new HashSet<T>();
    for (T item: original) {
        unique.add(item);
    }

    int size = unique.size();
    int curr = 0;
    for (int i = 0; i < original.length; i += 1) {
        if (unique.remove(original[i])) {
            original[curr] = original[i];
            curr++;
        }
    }

    return size;
}

これは、 O（n）を達​​成するためhashCodeに、リスト要素がのバケットに要素を適切に分散する方法に依存することに注意してください。HashSet最悪の場合、これはO（n * m）です。ここで、mは一意の要素の数であるため、確実に測定する必要があります。

この実装は、配置されている配列を変更し、一意の要素の数を返します。配列はこれよりも大きい場合がありますが、そのポイントを超える要素はガベージと見なす必要があります。

リストを1回通過してアイテムを追加しHashSet（アイテムの追加はO（1））、もう1回パスを実行して配列を更新するため、O（n）になります（これも、適切なハッシュ関数を想定しています）。

于 2012-10-09T18:43:38.467 に答える
0

これは、ハッシュと等しい比較のためにO（n）ではなく、Java標準ライブラリの一部であるLinkedHashSetを使用しますが、おそらく十分に近いです。

public void dups() {
    Set<Integer> uniques = new LinkedHashSet<>();
    for (int i = 0; i < elements.length; i++) {
        uniques.add(elements[i]);
    }
    // todo: copy the set into a list, then call toArray() to get an array.
}
于 2012-10-09T18:42:46.893 に答える
0

HashMapのデフォルトの実装は配列ベースであり、O（n）です。したがって、楽しい演習が必要な場合は、HashMapの実装をふるいにかけて、キーがどのようにハッシュされるかを正確に理解できます。基本的に、キーのhashCodeを使用し、それを使用して所定の場所（hashCode＆arraylength -1）の配列にインデックスを付け、そのインデックスに値を格納します。キーと値の両方として値を使用して概念を繰り返す場合、配列には一意のエントリのみが含まれます。

ただし、重複が多数あり、一意の値しかない場合は、空のスロットが多数ある配列になります。アレイにデータを入力したら、空のスロットを削除するために1回ループするだけで済みます。（例：null以外のすべてのエントリをリストにコピーします）

O（n）になりますが、2回のパスが必要です。1回はアレイにデータを入力し、もう1回は空のスロットを削除します。また、既存の配列と同じ長さの追加の配列と、一意の値の最終的なリスト用のより小さな配列（またはリスト）が必要になります。

于 2012-10-09T19:10:16.237 に答える