2

別の（類似した）質問に対するSOの回答として与えられたこのロジックに基づいて、 O（N）時間計算量の配列で繰り返される数値を削除するために、以下に示すように、そのロジックをCに実装しました。しかし、私のコードの結果は一意の番号を返しません。デバッグを試みましたが、これを修正するためのロジックを取得できませんでした。

int remove_repeat(int *a, int n)
{
    int i, k;

    k = 0;
    for (i = 1; i < n; i++)
    {
        if (a[k] != a[i]) 
        {
            a[k+1] = a[i];
            k++;            
        }
    }
    return (k+1);
}

main()
{
    int a[] = {1, 4, 1, 2, 3, 3, 3, 1, 5};
    int n;
    int i;

    n = remove_repeat(a, 9);

    for (i = 0; i < n; i++)
            printf("a[%d] = %d\n", i, a[i]);


}

1]重複を削除するための上記のコードの誤り。

2]この問題に対する他のO（N）またはO（NlogN）ソリューション。その論理？

4

7 に答える 7

2
  1. O（n log n）時間でのヒープソート。
  2. 繰り返し要素を番兵値（などINT_MAX）に置き換えて、O（n）時間で繰り返します。
  3. O（n log n）でヒープソートを再度実行して、繰り返し要素を抽出します。

まだO（n log n）で囲まれています。

于 2011-07-17T15:13:19.263 に答える
1

2つのループが必要になります。1つはソースを通過するためのもので、もう1つは宛先配列の各アイテムをチェックするためのものです。

O（N）を取得することはありません。

[編集]あなたがリンクした記事は 、出力配列内の重複の検索がバイナリ検索である可能性があることを意味するソートされた出力配列を提案しています...これはO（LogN）です。

于 2011-07-17T15:11:54.827 に答える
1

あなたのコードは、入力がソートされていることを要求しているように見えます。テストしているようにソートされていない入力を使用すると、コードはすべての重複を削除しません（隣接するもののみ）。

于 2011-07-17T15:14:26.683 に答える
1

整数の数が事前にわかっていて、持っているメモリの量よりも少ない場合は、O（N）ソリューションを取得できます:)。1回のパスで補助ストレージを使用している一意の整数を決定し、次に別のパスで一意の値を出力します。

以下のコードはJavaですが、うまくいけば、あなたはその考えを理解するでしょう。

int[] removeRepeats(int[] a) {
    // Assume these are the integers between 0 and 1000
    Boolean[] v = new Boolean[1000]; // A lazy way of getting a tri-state var (false, true, null)

    for (int i=0;i<a.length;++i) {
       v[a[i]] = Boolean.TRUE;
    } 

    // v[i] = null => number not seen
    // v[i] = true => number seen

    int[] out = new int[a.length];
    int ptr = 0;
    for (int i=0;i<a.length;++i) {
        if (v[a[i]] != null && v[a[i]].equals(Boolean.TRUE)) {
            out[ptr++] = a[i];
            v[a[i]] = Boolean.FALSE;          
        }
    }

    // Out now doesn't contain duplicates, order is preserved and ptr represents how
    // many elements are set.
    return out;
}
于 2011-07-17T15:22:51.837 に答える
1

コードは、配列内のアイテムがその直前のアイテムと同じであるかどうかのみをチェックします。

特定の番号のすべてのインスタンスが連続しているため、配列がソートされた状態で開始された場合、それは機能します。

配列が最初にソートされていない場合、特定の番号のインスタンスが連続していない可能性があるため、それは機能しません。したがって、先行するすべての番号を調べて、まだ表示されているかどうかを判断する必要があります。

O（N log N）時間でジョブを実行するには、配列を並べ替えてから、既に必要なロジックを使用して、並べ替えられた配列から重複を削除します。明らかに、これは、番号の再配置に問題がない場合にのみ役立ちます。

元の順序を保持したい場合は、ハッシュテーブルやビットセットなどを使用して、番号がまだ表示されているかどうかを追跡し、まだ表示されていない場合にのみ各番号を出力にコピーできます。これを行うために、現在のを変更します。

if (a[k] != a[i])
    a[k+1] = a[i];

次のようなものに：

if (!hash_find(hash_table, a[i])) { 
    hash_insert(hash_table, a[i]);
    a[k+1] = a[i];
}

数値がすべてかなり狭い範囲内にある場合、または値が密であると予想される場合（つまり、ほとんどの値が存在する場合）、ハッシュテーブルの代わりにビットセットを使用することをお勧めします。これはビットの配列であり、特定の数がまだ表示されているかどうかを示すために0または1に設定されます。

一方、平均的な場合よりも複雑さの上限に関心がある場合は、ハッシュテーブルの代わりにバランスの取れたツリーベースのコレクションを使用できます。これは通常、より多くのメモリを使用し、実行速度が遅くなりますが、予想される複雑さと最悪の場合の複雑さは基本的に同じです（O（N log N））。典型的なハッシュテーブルは、最悪の場合、一定の複雑さから線形の複雑さへと縮退します。これにより、全体的な複雑さがO（N）からO（N 2）に変わります。

于 2011-07-17T15:48:57.250 に答える
0

ロジックが間違っているので、コードも間違っています。コーディングする前に、自分でロジックを実行してください。ヒープソートを変更したO（NlnN）の方法を提案します。ヒープソートを使用して、a[i]からa[n]に結合し、最小値を見つけてa[i]に置き換えます。これが変更です。最小値がa[i-1]と同じである場合は、最小値とa [n]を入れ替えて、配列アイテムの数を1つ減らします。これでO（NlnN）の方法でトリックを実行できます。

于 2011-07-17T15:21:17.780 に答える
0

コードは特定の場合にのみ機能します。明らかに、隣接する値をチェックしていますが、配列内のどこでも重複する値が発生する可能性があります。したがって、それは完全に間違っています。

于 2011-07-17T17:20:30.643 に答える