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

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个缺失的数字。


当前回答

你可以试试布卢姆滤镜。将袋子中的每个数字插入到bloom中,然后遍历完整的1-k集,直到报告每个数字都没有找到。这可能不是在所有情况下都能找到答案,但可能是一个足够好的解决方案。

其他回答

你可以通过阅读Muthukrishnan的几页-数据流算法:谜题1:寻找缺失的数字来找到它。它准确地显示了您正在寻找的泛化。也许这就是面试官读到的内容,也是他提出这些问题的原因。


还请参阅sdcvvc的直接相关答案,其中还包括伪代码(万岁!没有必要阅读那些棘手的数学公式:)(谢谢,干得好!)

等一下。正如问题所述,袋子里有100个数字。无论k有多大,问题都可以在常数时间内解决,因为您可以使用一个集合,并在最多100k次循环迭代中从集合中删除数字。100是常数。剩下的数就是你的答案。

如果我们将解推广到从1到N的数字,除了N不是常数外,没有什么变化,所以我们在O(N - k) = O(N)时间内。例如,如果我们使用位集,我们在O(N)时间内将位设置为1,遍历这些数字,将位设置为0 (O(N-k) = O(N)),然后我们就得到了答案。

It seems to me that the interviewer was asking you how to print out the contents of the final set in O(k) time rather than O(N) time. Clearly, with a bit set, you have to iterate through all N bits to determine whether you should print the number or not. However, if you change the way the set is implemented you can print out the numbers in k iterations. This is done by putting the numbers into an object to be stored in both a hash set and a doubly linked list. When you remove an object from the hash set, you also remove it from the list. The answers will be left in the list which is now of length k.

你可以解出Q2如果你有两个链表的和和和两个链表的乘积。

(l1为原始列表,l2为修改后的列表)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

我们可以优化它,因为等差级数的和是第一项和最后一项的平均值的n倍:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

现在我们知道(如果a和b是被移除的数字):

a + b = d
a * b = m

所以我们可以重新排列为:

a = s - b
b * (s - b) = m

然后乘出来:

-b^2 + s*b = m

然后重新排列,使右边为零

-b^2 + s*b - m = 0

然后用二次公式求解:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Python 3示例代码:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

我不知道根号,减法和求和函数的复杂性,所以我无法计算出这个解决方案的复杂性(如果有人知道,请在下面评论)。

动机

如果您想解决一般情况下的问题,并且可以存储和编辑数组,那么到目前为止,Caf的解决方案是最有效的。如果您不能存储数组(流版本),那么sdcvvc的答案是目前建议的唯一解决方案类型。

我建议的解决方案是最有效的答案(到目前为止在这个线程中),如果你可以存储数组但不能编辑它,我从Svalorzen的解决方案中得到了这个想法,它解决了1或2个缺失的项目。该方案需要Θ(k*n)时间和O(min(k,log(n))和Ω(log(k))空间。它还可以很好地处理并行性。

概念

这个想法是,如果你使用原始的比较和的方法: sum = SumOf(1,n) - SumOf(数组)

... 然后取缺失数字的平均值: Average = sum/n_missing_numbers

…它提供了一个边界:在缺失的数字中,保证至少有一个数字小于或等于平均值,至少有一个数字大于平均值。这意味着我们可以分成子问题,每个子问题扫描数组[O(n)],并且只关心它们各自的子数组。

Code

c风格的解决方案(不要因为全局变量来评判我,我只是想让代码对非c语言的人来说可读):

#include "stdio.h"

// Example problem:
const int array [] = {0, 7, 3, 1, 5};
const int N = 8; // size of original array
const int array_size = 5;

int SumOneTo (int n)
{
    return n*(n-1)/2; // non-inclusive
}

int MissingItems (const int begin, const int end, int & average)
{
    // We consider only sub-array elements with values, v:
    // begin <= v < end
    
    // Initialise info about missing elements.
    // First assume all are missing:
    int n = end - begin;
    int sum = SumOneTo(end) - SumOneTo(begin);

    // Minus everything that we see (ie not missing):
    for (int i = 0; i < array_size; ++i)
    {
        if ((begin <= array[i]) && (array[i] < end))
        {
            --n;
            sum -= array[i];
        }
    }
    
    // used by caller:
    average = sum/n;
    return n;
}

void Find (const int begin, const int end)
{
    int average;

    if (MissingItems(begin, end, average) == 1)
    {
        printf(" %d", average); // average(n) is same as n
        return;
    }
    
    Find(begin, average + 1); // at least one missing here
    Find(average + 1, end); // at least one here also
}

int main ()
{   
    printf("Missing items:");
    
    Find(0, N);
    
    printf("\n");
}

分析

暂时忽略递归,每个函数调用显然需要O(n)时间和O(1)空间。请注意,sum可以等于n(n-1)/2,因此需要存储n-1所需的位数的两倍。这最多意味着我们实际上需要两个额外的元素的空间,不管数组或k的大小,因此它仍然是O(1)个空间。

对于k个缺失的元素有多少函数调用不是很明显,所以我将提供一个可视化的。原始子数组(连通数组)是完整数组,其中包含所有k个缺失元素。我们将把它们想象成递增的顺序,其中-表示连接(同一子数组的一部分):

M1—m2—m3—m4—(…)—mk-1—mk

Find函数的作用是将缺失的元素断开连接到不同的非重叠子数组中。它保证每个子数组中至少有一个缺失元素,这意味着恰好断开一个连接。

这意味着无论分割是如何发生的,它总是使用k-1 Find函数调用来查找只缺少一个元素的子数组。

那么时间复杂度为Θ((k-1 + k) *n) = Θ(k*n)。

对于空间复杂度,如果我们每次按比例分割,就会得到O(log(k))个空间复杂度,但如果我们每次只分离一个,就会得到O(k)个空间复杂度。

这里有一个关于为什么空间复杂度是O(log(n))的证明。鉴于上面我们已经证明了它也是O(k)那么我们知道它是O(min(k,log(n)))

我使用Java 8和Java 8之前的版本编写代码。 它使用一个公式:(N*(N+1))/2作为所有数字的和。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

   /**
 * 
 * 
 * @author pradeep
 * 
 *         Answer : SumOfAllNumbers-SumOfPresentNumbers=Missing Number;
 * 
 *         To GET SumOfAllNumbers : Get the highest number (N) by checking the
 *         length. and use the formula (N*(N+1))/2
 * 
 *         To GET SumOfPresentNumbers: iterate and add it
 * 
 * 
 */
public class FindMissingNumber {
    /**
     * Before Java 8
     * 
     * @param numbers
     * @return
     */
    public static int missingNumber(List<Integer> numbers) {
        int sumOfPresentNumbers = 0;
        for (Integer integer : numbers) {
            sumOfPresentNumbers = sumOfPresentNumbers + integer;
        }
        int n = numbers.size();
        int sumOfAllNumbers = (n * (n + 1)) / 2;
        return sumOfAllNumbers - sumOfPresentNumbers;
    }
    /**
     * Using Java 8 . mapToInt & sum using streams.
     * 
     * @param numbers
     * @return
     */
    public static int missingNumberJava8(List<Integer> numbers) {
        int sumOfPresentNumbers = numbers.stream().mapToInt(i -> i).sum();
        int n = numbers.size();
        int sumOfAllNumbers = (n * (n + 1)) / 2;
        return sumOfAllNumbers - sumOfPresentNumbers;
    }
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list = Arrays.asList(0, 1, 2, 4);
        System.out.println("Missing number is :  " + missingNumber(list));
        System.out.println("Missing number using Java 8 is : " + missingNumberJava8(list));
    }
}*