这是个很简单的问题

void findMissing(){
    bool record[N] = {0};
    for(int i = 0; i < N; i++){
        record[bag[i]-1] = 1;
    }
    for(int i = 0; i < N; i++){
        if(!record[i]) cout << i+1 << endl;
    }
}

O(n)时间和空间复杂度

如果一个数字只出现一次，用下面的方法很容易分辨:

创建一个大小为给定数字的布尔数组boolArray;这里是100。

遍历输入数字，并根据数字值将一个元素设置为true。例如，如果找到45，则设置boolArray[45-1] = true;

这是一个O(N)运算。

然后循环遍历boolArray。如果一个元素保持为false，那么element + 1的下标就是缺失的数字。例如，如果boolArray[44]为false，我们就知道第45号丢失了。

这是O(n)运算。空间复杂度为O(1)。

所以这个解可以从一个给定的连续数集中找到任何缺失的数。

您可能需要澄清O(k)的含义。

这里有一个任意k的简单解:对于你的数字集中的每一个v，将2^v相加。最后，循环i从1到n，如果和2^i按位和为零，则i缺失。(或者在数字上，如果和的底除以2^i是偶数。或者模2^(i+1) < 2^i

容易,对吧?O(N)时间，O(1)存储，支持任意k。

除了你在计算一个巨大的数字，在真正的计算机上，每个数字都需要O(N)个空间。事实上，这个解和位向量是一样的。

所以你可以很聪明地计算和，平方和和和立方体的和…直到v^k的和，然后用复杂的数学方法提取结果。但这些都是很大的数字，这就引出了一个问题:我们谈论的是哪种抽象的运作模式?O(1)空间中有多少是合适的，以及需要多长时间才能将所需大小的数字相加?

我们可以通过把数字本身和这些数字的平方相加来解Q2。

我们可以把问题简化为

k1 + k2 = x
k1^2 + k2^2 = y

其中x和y表示和低于期望值的程度。

代换给我们:

(x-k2)^2 + k2^2 = y

然后我们可以解出缺失的数。

基于数字和的解决方案的问题是，它们没有考虑到存储和处理具有大指数的数字的成本……在实践中，为了使它适用于非常大的n，将使用大数库。我们可以分析这些算法的空间利用率。

我们可以分析sdcvvc和Dimitris Andreou算法的时间和空间复杂度。

储存:

l_j = ceil (log_2 (sum_{i=1}^n i^j))
l_j > log_2 n^j  (assuming n >= 0, k >= 0)
l_j > j log_2 n \in \Omega(j log n)

l_j < log_2 ((sum_{i=1}^n i)^j) + 1
l_j < j log_2 (n) + j log_2 (n + 1) - j log_2 (2) + 1
l_j < j log_2 n + j + c \in O(j log n)`

所以l_j \in \ (j log n)

所使用的总存储空间:\sum_{j=1}^k l_j \in \Theta(k^2 log n)

使用的空间:假设计算a^j需要ceil(log_2 j)时间，总时间:

t = k ceil(\sum_i=1^n log_2 (i)) = k ceil(log_2 (\prod_i=1^n (i)))
t > k log_2 (n^n + O(n^(n-1)))
t > k log_2 (n^n) = kn log_2 (n)  \in \Omega(kn log n)
t < k log_2 (\prod_i=1^n i^i) + 1
t < kn log_2 (n) + 1 \in O(kn log n)

总使用时间:\Theta(kn log n)

如果这个时间和空间是令人满意的，您可以使用一个简单的递归 算法。让b !I是袋子里的第I个元素，n个之前的数字 移除次数，k是移除次数。在Haskell语法中…

let
  -- O(1)
  isInRange low high v = (v >= low) && (v <= high)
  -- O(n - k)
  countInRange low high = sum $ map (fromEnum . isInRange low high . (!)b) [1..(n-k)]
  findMissing l low high krange
    -- O(1) if there is nothing to find.
    | krange=0 = l
    -- O(1) if there is only one possibility.
    | low=high = low:l
    -- Otherwise total of O(knlog(n)) time
    | otherwise =
       let
         mid = (low + high) `div` 2
         klow = countInRange low mid
         khigh = krange - klow
       in
         findMissing (findMissing low mid klow) (mid + 1) high khigh
in
  findMising 1 (n - k) k

使用的存储:O(k)用于列表，O(log(n))用于堆栈:O(k + log(n)) 该算法更直观，具有相同的时间复杂度，占用的空间更少。

非常好的问题。我会用Qk的集合差。很多编程语言甚至都支持它，比如Ruby:

missing = (1..100).to_a - bag

这可能不是最有效的解决方案，但如果我在这种情况下面临这样的任务(已知边界，低边界)，这是我在现实生活中会使用的解决方案。如果数字集非常大，那么我当然会考虑一个更有效的算法，但在此之前，简单的解决方案对我来说已经足够了。