arrays - 查找数组中缺失的数字，时间复杂度O(N)，空间复杂度O(1)

Question

给定一个包含 n 个唯一整数的数组 0 <= x_i < 2 * n。打印此数组中不存在的所有整数 0 <= x < 2 * n。

例子:

find_missing([0]) = [1]

find_missing([0, 2, 4]) = [1, 3, 5] # 因为所有数字都是[0, 1, 2, 3, 4, 5]

查找缺失([]) = []

find_missing([0, 1, 4, 5]) = [2, 3, 6, 7] # 因为所有数字都是[0, 1, 2, 3, 4, 5, 6, 7]

怪癖与要求有关:

时间复杂度 O(n) - 但是应该有一些独立于输入大小的固定常量 C，这样数组的每个元素都被写入/读取 < C 次，因此基数排序数组是不行的。

空间复杂度 O(1) - 你可以修改初始数组，但是 sorted(initial_array) 必须等于 sorted(array_after_executing_program) 并且你不能在这个数组中存储范围 [0, 2n) 之外的整数(假设它是一个uint32_t 数组)。

我看到了很多复杂的解决方案，但后来我发现了这个:

public void printNotInArr(int[] arr) {
    if(arr == null)
        return null;

    int len = arr.length;
    int max = 2 * len;

    for(int i = 0; i < len; i++) {
        System.out.println(max - arr[i] - 1);
    }
}

我相信这是最好的解决方案，但我不确定。我想知道为什么那行不通。

Answer 1

正如@LasseV.Karlsen 所指出的，[0,3] 是一个简单的反例，它显示了该解决方案如何不起作用。然而，这是一个非常简单的解决方案(在 Python 中):

def show_missing(l):
  n = len(l)

  # put numbers less than n into the proper slot
  for i in range(0,n):
    while l[i]<n and l[i]!=i:
      j = l[i]
      l[i] = l[j]
      l[j] = j
  for i in range(0,n):
    if l[i]!=i:
      print('Missing %s'%i)

  # put numbers greater than n into the proper slot
  for i in range(0,n):
    while l[i]>=n and l[i]!=i+n:
      j = l[i]
      l[i] = l[j-n]
      l[j-n] = j
  for i in range(0,n):
    if l[i]!=i+n:
      print('Missing %s'%(i+n))

这个想法很简单。我们首先重新排列元素，以便每个小于 n 的值 j 都存储在索引 j 处。然后我们可以遍历数组并轻松找出 n 以下缺失的数组。

然后我们重新排列元素，以便每个大于或等于 n 的值 j 都存储在索引 j-n 中。同样，我们可以遍历数组并轻松挑选出大于或等于 n 的缺失值。

由于只使用了几个局部变量，所以满足 O(1) 空间复杂度。

由于嵌套循环，O(n) 的时间复杂度有点难以看出，但不难证明我们永远不会交换超过 n 个元素，因为一个新元素被放入其适当的位置放置在每次交换中。

由于我们只是交换了数组的元素，所以所有原始元素仍在数组中的要求也得到满足。