在数组中找到缺失的数字，时间复杂度为O（N），空间复杂度为O（1）。

Question

在数组中找到缺失的数字，时间复杂度为O（N），空间复杂度为O（1）。

3

你将获得一个包含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([]) = [] 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);
    }
}

我认为那是最佳解决方案，但我不确定。我想知道为什么那样做行不通。

- user3259176

1

既然它不能做你要求的事情，那么它根本不是一个解决方案。尝试传入0, 3。你会得到3, 0，很明显它根本没有输出缺失的数字。 - Lasse V. Karlsen

输入是否保证已排序，就像所有示例中一样？ - Joni

这不同于那个问题，因为那个问题只是移除了一个数字。这是一个完全不同的问题，有一个简单的解决方案。这里的问题不同，可能会缺少多个数字。那个问题的简单解决方案在这里不起作用。 - Lasse V. Karlsen

我现在看到，如果两个元素互补，则会出现错误。例如，如果Max = 3，arr = [0, 3]，则0 + 3 = 3 = Max。arr = [1,2] -> rs [2,1]，并且2 + 1 = 3。 - user3259176

两个本地变量可以被视为O(1)的空间复杂度，因此只需使用一个变量作为索引，另一个变量用于存储数组中下一个预期的值，并对数组进行一次遍历。 - rcgldr

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vaughn Cato · Accepted Answer

正如@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个元素，因为每次交换都将一个新元素放入其正确的位置。

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