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

Question

背景:

我有一个长度为 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 个 boolean 数组来跟踪已使用/未使用的数字([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 实现，因为它更完整。

Answer 1

使用 balanced binary search tree跟踪使用/未使用的数字而不是 boolean 数组。那么你的运行时间将是 n log n。

最直接的解决方案是:

1. 遍历列表并构建“未使用的”BST
2. 第二次浏览列表，跟踪到目前为止在“使用过的”BST 中看到的数字
3. 如果找到重复项，将其替换为“未使用”BST 的随机元素。