你能查一下每个号码是否都存在吗?如果是，你可以试试这个:

S =袋子中所有数字的和(S < 5050) Z =缺失数的和5050 - S

如果缺失的数字是x和y，则:

x = Z - y和 max(x) = Z - 1

所以你检查从1到max(x)的范围，并找到这个数字

You can motivate the solution by thinking about it in terms of symmetries (groups, in math language). No matter the order of the set of numbers, the answer should be the same. If you're going to use k functions to help determine the missing elements, you should be thinking about what functions have that property: symmetric. The function s_1(x) = x_1 + x_2 + ... + x_n is an example of a symmetric function, but there are others of higher degree. In particular, consider the elementary symmetric functions. The elementary symmetric function of degree 2 is s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n, the sum of all products of two elements. Similarly for the elementary symmetric functions of degree 3 and higher. They are obviously symmetric. Furthermore, it turns out they are the building blocks for all symmetric functions.

你可以通过注意s_2(x,x_(n+1)) = s_2(x) + s_1(x)(x_(n+1))来构建初等对称函数。进一步思考应该会使您相信s_3(x,x_(n+1)) = s_3(x) + s_2(x)(x_(n+1))等等，因此它们可以在一次传递中计算。

我们如何知道数组中缺少了哪些项?考虑多项式(z-x_1) (z-x_2)……(z-x_n)。如果你输入任意一个数字x_i，它的值都是0。展开多项式，得到z^n-s_1(x)z^(n-1)+。+ (-1)^n s_n。初等对称函数也出现在这里，这并不奇怪，因为多项式应该保持不变，如果我们对根进行任何排列。

所以我们可以建立一个多项式，并尝试因式分解来找出哪些数不在集合中，就像其他人提到的那样。

Finally, if we are concerned about overflowing memory with large numbers (the nth symmetric polynomial will be of the order 100!), we can do these calculations mod p where p is a prime bigger than 100. In that case we evaluate the polynomial mod p and find that it again evaluates to 0 when the input is a number in the set, and it evaluates to a non-zero value when the input is a number not in the set. However, as others have pointed out, to get the values out of the polynomial in time that depends on k, not N, we have to factor the polynomial mod p.

假设一个ArrayList对象(myList)被这些数字填充，其中x和y两个数字缺失。所以可能的解决方案是:

int k = 1;
        while (k < 100) {
            if (!myList.contains(k)) {
                System.out.println("Missing No:" + k);
            }
            k++;
        }

我让一个4岁的孩子来解决这个问题。他把数字分类，然后开始数。这有一个O(厨房地板)的空间要求，它的工作就像许多球丢失一样简单。

我们可以使用下面的简单代码来查找重复的和缺失的值:

    int size = 8;
    int arr[] = {1, 2, 3, 5, 1, 3};
    int result[] = new int[size];

    for(int i =0; i < arr.length; i++)
    {
        if(result[arr[i]-1] == 1)
        {
            System.out.println("repeating: " + (arr[i]));
        }
        result[arr[i]-1]++;
    }

    for(int i =0; i < result.length; i++)
    {
        if(result[i] == 0)
        {
            System.out.println("missing: " + (i+1));
        }
    }

要解决缺少2(和3)个数字的问题，您可以修改quickselect，它平均在O(n)内运行，如果分区是就地完成的，则使用恒定内存。

Partition the set with respect to a random pivot p into partitions l, which contain numbers smaller than the pivot, and r, which contain numbers greater than the pivot. Determine which partitions the 2 missing numbers are in by comparing the pivot value to the size of each partition (p - 1 - count(l) = count of missing numbers in l and n - count(r) - p = count of missing numbers in r) a) If each partition is missing one number, then use the difference of sums approach to find each missing number. (1 + 2 + ... + (p-1)) - sum(l) = missing #1 and ((p+1) + (p+2) ... + n) - sum(r) = missing #2 b) If one partition is missing both numbers and the partition is empty, then the missing numbers are either (p-1,p-2) or (p+1,p+2) depending on which partition is missing the numbers. If one partition is missing 2 numbers but is not empty, then recurse onto that partiton.

由于只缺少2个数字，该算法总是丢弃至少一个分区，因此保持了O(n)个快速选择的平均时间复杂度。类似地，当缺少3个数字时，该算法也会在每次传递中丢弃至少一个分区(因为当缺少2个数字时，最多只有1个分区包含多个缺少的数字)。然而，我不确定当添加更多缺失的数字时，性能会下降多少。

下面是一个不使用就地分区的实现，所以这个例子不满足空间要求，但它确实说明了算法的步骤:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Demo