用0-(N-1)中的唯一数字替换重复的数字

Question

背景:

我有一个N长度的正随机数组,肯定包含重复项.例如10,4,5,7,10,9,10,9,8,10,5
编辑:N很可能是32,或者说是那个大小的其他两个幂.

问题:

我试图找到用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;
}  

这似乎是我所希望的最快,但我想我会问互联网,因为有些人比我更聪明可能有更好的解决方案.

NB建议/解决方案不一定是Java.

谢谢.

编辑:我忘了提到我正在将其转换为C++.我发布了我的java实现,因为它更完整.

Answer 1

使用平衡二进制搜索树来跟踪已使用/未使用的数字而不是布尔数组.那你就是运行时间n log n.

最直接的解决方案是:

1. 浏览列表并构建"未使用的"BST
2. 再次浏览列表,跟踪到目前为止在"二手"BST中看到的数字
3. 如果找到重复项,请将其替换为"未使用的"BST的随机元素.

Answer 2

最快的方法可能是最直接的方法。我将遍历数据列表，记录每个不同值的计数并标记出现重复项的位置。然后，只需形成一个未使用值的列表，并将它们依次应用到发现重复项的位置即可。

尽管使用 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