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 ，而不只是用 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

My approach would be 1. copy the array to a Set in Java.

Set will automatically remove duplicates in the fastest complexity possible(because Sun Micro has implemented it, generally their approach is the fastest like.. use of TimSort for sorting etc...)

  1. Calculate size() of the set.

  2. the size will give you no of duplicates present.

  3. now copy array 0-n-1 to the same set... the missing values will get inserted.

于 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 
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 内运行。列表操作是常数时间，即使第二个循环看起来是嵌套的，外循环运行的次数明显少于 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 回答
0

我认为它甚至可以运行 time 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 回答