algorithm - 对元素范围为 1 到 n 的给定数组进行排序，其中一个元素缺失，一个元素重复

Question

我必须在 O(n) 时间和 O(1) 空间内对这个数组进行排序。

我知道如何在 O(n) 中对数组进行排序，但这不适用于丢失和重复的数字。如果我先找到重复和缺失的数字(可以在 O(n) 中完成)然后排序，这似乎很昂贵。

static void sort(int[] arr)
{
    for(int i=0;i<arr.length;i++)
    {
        if(i>=arr.length)
            break;
        if(arr[i]-1 == i)
            continue;
        else
        {
        while(arr[i]-1 != i)
        {
            int temp = arr[arr[i]-1];
            arr[arr[i]-1] = arr[i];
            arr[i] = temp;
        }
        }
    }
}

Answer 1

首先，您需要找到缺失和重复的数字。您可以通过求解以下方程组来做到这一点:

通过遍历数组同时计算左和。右和甚至更简单——您可以使用算术级数的公式来避免循环。所以，现在您有了两个方程组，其中有两个未知数:缺失数 m 和重复数 r。解决它。

接下来，您通过从左到右用数字 1 到 n 填充数组来“排序”数组，省略 m 并复制 r。因此，整个算法只需要两次遍历数组。