6

バックグラウンド：

重複が確実に含まれる正の乱数のN長配列があります。例：10,4,5,7,10,9,10,9,8,10,5
編集：Nは32、またはそのサイズの2のその他の累乗である可能性があります。

問題：

重複を0から（N-1）までの欠落している番号に置き換える最速の方法を見つけようとしています。上記の例を使用して、次のような結果が必要です
。10,4,5,7,0,9,1,2,8,3,6
目標は、0からN-1までの各数値の1つを持つことです。 、すべての数字を0-（N-1）に置き換えるだけではありません（ランダムな順序が重要です）。
編集：この置換が決定論的であることも重要です。つまり、同じ入力が同じ出力（ランダムではない）を持ちます。

私の解決策：

現在Javaで実装されており、2つのブール配列を使用して使用済み/未使用の数値（[0、N）の範囲の一意の数値/欠落している数値）を追跡し、おおよその最悪の場合の実行時間はN + N * sqrt（N）です。 。
コードは次のとおりです。 

public byte[] uniqueify(byte[] input)
{
    boolean[] usedNumbers = new boolean[N];
    boolean[] unusedIndices = new boolean[N];
    byte[] result = new byte[N];

    for(int i = 0; i < N; i++) // first pass through
    {
        int newIdx = (input[i] + 128) % N; // first make positive
        if(!usedNumbers[newIdx]) // if this number has not been used
        {
            usedNumbers[newIdx] = true; // mark as used
            result[i] = newIdx; // save it in the result
        }
        else // if the number is used
        {
            unusedIndices[i] = true; // add it to the list of duplicates
        }
    }

    // handle all the duplicates
    for(int idx = 0; idx < N; idx++) // iterate through all numbers
    {
        if(unusedIndices[idx]) // if unused
            for(int i = 0; i < N; i++) // go through all numbers again
            {
                if(!usedNumbers[i]) // if this number is still unused
                {
                    usedNumbers[i] = true; // mark as used
                    result[i] = idx;
                    break;
                }
            }
    }
    return result;
}

これは私が望むことができる最速のように思えますが、私よりもはるかに賢い人々がより良い解決策を持っているかもしれないので、私はインターネットに尋ねると思いました。

注意：提案/解決策はJavaである必要はありません。

ありがとうございました。

編集：私はこれをC++に変換していることを言及するのを忘れました。より完全なので、Java実装を投稿しました。

4

7 に答える 7

5

ブール配列の代わりに、平衡二分探索木を使用して、使用済み/未使用の数値を追跡します。次に、実行時間はになりますn log n。

最も簡単な解決策は次のとおりです。

  1. リストに目を通し、「未使用」のBSTを作成します
  2. 「使用済み」BSTでこれまでに見られた数を追跡しながら、リストをもう一度確認します
  3. 重複が見つかった場合は、「未使用」のBSTのランダムな要素に置き換えます。
于 2012-04-06T08:21:03.090 に答える
2

これが私がそれを書く方法です。

public static int[] uniqueify(int... input) {
    Set<Integer> unused = new HashSet<>();
    for (int j = 0; j < input.length; j++) unused.add(j);
    for (int i : input) unused.remove(i);
    Iterator<Integer> iter = unused.iterator();
    Set<Integer> unique = new LinkedHashSet<>();
    for (int i : input)
        if (!unique.add(i))
            unique.add(iter.next());
    int[] result = new int[input.length];
    int k = 0;
    for (int i : unique) result[k++] = i;
    return result;
}

public static void main(String... args) {
    System.out.println(Arrays.toString(uniqueify(10, 4, 5, 7, 10, 9, 10, 9, 8, 10, 5)));
}

プリント

[10, 4, 5, 7, 0, 9, 1, 2, 8, 3, 6]
于 2012-04-06T08:31:08.897 に答える
1

私のアプローチは次のとおりです。1。配列をJavaのセットにコピーします。

Setは、可能な限り最速の複雑さで重複を自動的に削除します（Sun Microが実装しているため、通常、それらのアプローチは、ソートなどにTimSortを使用するなどの最速です）。

  1. セットのsize（）を計算します。

  2. サイズはあなたに存在する重複を与えません。

  3. ここで、配列0-n-1を同じセットにコピーします...欠落している値が挿入されます。

于 2012-04-06T08:25:33.123 に答える
1

これを行う最も速い方法は、おそらく最も簡単な方法です。データのリストを調べて、それぞれの個別の値のカウントを保持し、重複が発生した場所をマークします。次に、未使用の値のリストを作成し、重複が見つかった場所に順番に適用するだけです。

C ++を使用するListのも魅力的ですが、速度が重要な場合は、単純なC配列が最も効率的です。

このプログラムは原理を示しています。

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
  int data[] = { 10, 4, 5, 7, 10, 9, 10, 9, 8, 10, 5 };
  int N = sizeof(data) / sizeof(data[0]);

  int tally[N];
  memset(tally, 0, sizeof(tally));

  int dup_indices[N];
  int ndups = 0;

  // Build a count of each value and a list of indices of duplicate data
  for (int i = 0; i < N; i++) {
    if (tally[data[i]]++) {
      dup_indices[ndups++] = i;
    }
  }

  // Replace each duplicate with the next value having a zero count
  int t = 0;
  for (int i = 0; i < ndups; i++) {
    while (tally[t]) t++;
    data[dup_indices[i]] = t++;
  }

  for (int i = 0; i < N; i++) {
    cout << data[i] << " ";
  }

  return 0;
}

出力

10 4 5 7 0 9 1 2 8 3 6
于 2012-04-07T01:38:02.053 に答える
0

実行時間でも可能だと思いますn。アイデアは、元のリストで使用されたアイテムと、処理中に使用された追加のアイテムを別の配列で追跡することです。可能なJava実装は次のようになります。

int[] list = { 10, 4, 5, 7, 10, 9, 10, 9, 8, 10, 5 };

boolean[] used = new boolean[list.length];
for (int i : list) {
    used[i] = true;
}

boolean[] done = new boolean[list.length];
int nextUnused = 0;

Arrays.fill(done, false);

for (int idx = 0; idx < list.length; idx++) {
    if (done[list[idx]]) {
        list[idx] = nextUnused;
    }
    done[list[idx]] = true;
    while (nextUnused < list.length && (done[nextUnused] || used[nextUnused])) {
        nextUnused++;
    }
}

System.out.println(Arrays.toString(list));
于 2012-04-06T08:30:53.790 に答える
0 
List<Integer> needsReplaced = newLinkedList<Integer>();
boolean[] seen = new boolean[input.length];

for (int i = 0; i < input.length; ++i) {
    if (seen[input[i]]) {
        needsReplaced.add(i);
    } else {
        seen[input[i]] = true;
    }

}

int replaceWith = 0;
for (int i : needsReplaced) {
    while (seen[replaceWith]) {
        ++replaceWith;
    }
    input[i] = replaceWith++;
}

これは約2nで動作するはずです。リスト操作は一定時間であり、その2番目のループはネストされているように見えますが、外側のループはn回よりも大幅に少なく実行され、内側のループは合計n回しか実行されません。

于 2012-04-06T09:42:34.190 に答える
0

C＃ですが、Javaに簡単に変換できるはずです。の上）。

        int[] list = { 0, 0, 6, 0, 5, 0, 4, 0, 1, 2, 3 };
        int N = list.length;

        boolean[] InList = new boolean[N];
        boolean[] Used = new boolean[N];
        int[] Unused = new int[N];

        for (int i = 0; i < N; i++) InList[list[i]] = true;
        for (int i = 0, j = 0; i < N; i++) 
            if (InList[i] == false)
                Unused[j++] = i;

        int UnusedIndex = 0;
        for (int i = 0; i < N; i++)
        {
            if (Used[list[i]] == true)
                list[i] = Unused[UnusedIndex++];
            Used[list[i]] = true;
        }

編集：C＃からJavaに変換しようとしました。ここにはJavaがないので、コンパイルされない可能性がありますが、簡単に修正できるはずです。Javaが自動的に初期化しない場合は、配列をfalseに初期化する必要があります。

于 2012-04-06T09:58:03.487 に答える