前段时间我有一次有趣的面试经历。问题一开始很简单:

Q1:我们有一个袋子,里面有数字1,2,3,…,100。每个数字恰好出现一次,所以有100个数字。现在从袋子里随机抽取一个数字。找到丢失的号码。

当然,我以前听过这个面试问题,所以我很快就回答了这个问题:

A1:嗯,1 + 2 + 3 +…+ N的和是(N+1)(N/2)(参见维基百科:等差级数的和)。当N = 100时,和是5050。 因此,如果所有的数字都在袋子里,总和将恰好是5050。因为少了一个数,总和就会小于这个数,差的就是这个数。所以我们可以在O(N)时间和O(1)空间中找到这个缺失的数。

在这一点上,我认为我做得很好,但突然间,问题发生了意想不到的转变:

这是正确的,但是如果少了两个数字,你会怎么做?

我以前从未见过/听过/考虑过这种变化,所以我很恐慌,无法回答这个问题。面试官坚持要知道我的思考过程,所以我提到,也许我们可以通过与预期产品进行比较来获得更多信息,或者在从第一次传递中收集到一些信息后再进行第二次传递,等等,但我真的只是在黑暗中拍摄,而不是真正有一个明确的解决方案的路径。

面试官试图鼓励我说,有第二个方程确实是解决问题的一种方法。在这一点上,我有点不安(因为事先不知道答案),并问这是一种通用的(阅读:“有用的”)编程技术,还是只是一个技巧/答案。

面试官的回答让我惊讶:你可以把这个技巧概括为3个缺失的数字。事实上,你可以推广它来找到k个缺失的数。

Qk:如果袋子里少了k个数字,你如何有效地找到它?

这是几个月前的事了,我还不明白这个技巧是什么。显然有一个Ω(N)的时间下限,因为我们必须扫描所有的数字至少一次,但面试官坚持认为,解决技术的时间和空间复杂度(减去O(N)次输入扫描)定义为k而不是N。

所以问题很简单:

如何解决Q2? 你会如何解决Q3? 如何求解Qk?


澄清

Generally there are N numbers from 1..N, not just 1..100. I'm not looking for the obvious set-based solution, e.g. using a bit set, encoding the presence/absence each number by the value of a designated bit, therefore using O(N) bits in additional space. We can't afford any additional space proportional to N. I'm also not looking for the obvious sort-first approach. This and the set-based approach are worth mentioning in an interview (they are easy to implement, and depending on N, can be very practical). I'm looking for the Holy Grail solution (which may or may not be practical to implement, but has the desired asymptotic characteristics nevertheless).

当然,你必须以O(N)为单位扫描输入,但你只能捕获少量的信息(用k而不是N定义),然后必须以某种方式找到k个缺失的数字。


当前回答

对于不同的k值,方法将是不同的,所以不会有一个关于k的通用答案。例如,对于k=1,可以利用自然数和,但对于k= n/2,必须使用某种bitset。对于k=n-1也是一样,我们可以简单地将袋子里唯一的数字与其他数字进行比较。

其他回答

我认为可以这样概括:

表示S, M为等差级数和乘法的初始值。

S = 1 + 2 + 3 + 4 + ... n=(n+1)*n/2
M = 1 * 2 * 3 * 4 * .... * n 

我应该考虑一个公式来计算这个,但这不是重点。无论如何,如果缺少一个数字,您已经提供了解决方案。但是,如果少了两个数字,让我们用S1和M1表示新的和和和总倍数,如下所示:

S1 = S - (a + b)....................(1)

Where a and b are the missing numbers.

M1 = M - (a * b)....................(2)

因为你知道S1 M1 M和S,上面的方程是可以解出a和b,缺失的数字。

现在来看看遗漏的三个数字:

S2 = S - ( a + b + c)....................(1)

Where a and b are the missing numbers.

M2 = M - (a * b * c)....................(2)

现在未知量是3而你只有两个方程可以解。

关键是使用索引来标记范围内是否存在某个数字。 这里我们知道从1到N。 时间复杂度O(n) 空间复杂度O(1)

后续问题: 这可以被修改为发现一个元素是否从差值为d的AP中缺失。其他变化可能包括从任何包含-ve数的随机数组中查找第一个缺失的+ve数。然后先对0左右的分区进行快速排序,然后对分区右侧的数组部分做此程序,做必要的修改。

public static void  missing(int [] arr){        
      for(int i=0; i< arr.length; i++){       
          if(arr[i]!=-1 && arr[i]<=arr.length){
              int idx=i;
              while(idx>=0 && idx<arr.length&& arr[idx]!=-1 ){
                   int temp =arr[idx];
                   // temp-1 because array index starts from 0, i.e a[0]=-1 is indicates that 1 is present in the array
                   arr[temp-1]=-1;
                   idx=temp-1;
              }
          }
      }
    }

在此之后,我们需要迭代数组,并检查是否a[i]!=-1,那么i+1就是缺失的数。当a[i]>N时,我们必须小心。

基于数字和的解决方案的问题是,它们没有考虑到存储和处理具有大指数的数字的成本……在实践中,为了使它适用于非常大的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)) 该算法更直观,具有相同的时间复杂度,占用的空间更少。

您可能需要澄清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)空间中有多少是合适的,以及需要多长时间才能将所需大小的数字相加?

要解决缺少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