小编Anr*_*nro的帖子

背景:

我有一个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 …