简单的面试问题变得更难了:给定数字1..100,找出缺失的数字

以下是对 Dimitris Andreou's link .

记住i次方的和,其中i=1,2,…,k。这就把问题简化为求解方程组

一 ₁ +a + ... + 一 =b级 ₁

₁ ² +a ² _k =b级

...

一 ₁ ^k +a ₂ ^k =b级 _k

使用 Newton's identities ,了解b _我

_{1 1} +a _{2 k}

c _{2 1 2 1 三 k-1公司 k}

...

c _k 一 ₂ ... 一

如果展开多项式(x-a ₁ )…(x-a) )系数正好是c _k Viète's formulas . 因为每个多项式因子都是唯一的(多项式环是一个 Euclidean domain ),这意味着 是唯一确定的,直到排列。

这就结束了一个证明:记住幂足以恢复数字。对于常数k,这是一个很好的方法。

然而,当k变化时,计算c的直接方法 ₁ ,…,c _{k k} computations in Z _q field ,其中q是素数,使得n<=问题<2n-它存在于 Bertrand's postulate . 证明不需要改变,因为公式仍然成立,多项式的因式分解仍然是唯一的。您还需要一个有限域上的因式分解算法,例如one by Berlekamp Cantor-Zassenhaus .

• 计算给定数的i次幂
• _我
• 利用牛顿恒等式计算b _{我 我 1} =b级 ; c ₂ =(c) _{1 1} -b类 ₂
• 多项式x的因子 ^k -c级 ₁ 十 + ... + c _k
• 多项式的根是a所需要的数 _{1 k}

对于变k,求素数n<=问题<2n使用例如Miller-Rabin,并用所有数的约化模q执行步骤。

编辑:这个答案的前一个版本说,而不是Z _q ,其中q是素数,可以使用特征2的有限域(q=2^(logn))。事实并非如此,因为牛顿的公式需要除以k以内的数。

Muthukrishnan - Data Stream Algorithms: Puzzle 1: Finding Missing Numbers . 它准确地显示了你正在寻找的概括 . 也许这就是你的面试官读到的,以及他提出这些问题的原因。

另请参见 sdcvvc's 直接相关答案 ,其中还包括伪代码(万岁!不用看那些复杂的数学公式:)(谢谢,做得好!)。

方块字 数字的一部分。

然后我们可以把问题简化为

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

在哪里? x y 总和低于预期值的程度。

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

正如@j\u random\u hacker指出的,这与 Finding duplicates in O(n) time and O(1) space 我的答案在这里也适用。

假设“bag”由一个基于1的数组表示 A[] N - k O(N) 时间和 O(k) 额外空间。

首先,我们扩展阵列 A[] k 元素,所以它现在的大小 N . 这就是

for i := n - k + 1 to n
    A[i] := A[1]
end for

for i := 1 to n - k
    while A[A[i]] != A[i] 
        swap(A[i], A[A[i]])
    end while
end for

for i := 1 to n
    if A[i] != i then 
        print i
    end if
end for

k 与数组中的第一个条目相同的额外条目(这只是一个方便的值,我们知道它已经存在于数组中—在此步骤之后,任何在大小的初始数组中丢失的条目 N-k

第二个循环排列扩展数组,以便if元素 x A[x] .

O(N) 时间-只有在存在 i A[i] != i ,每个交换设置至少一个元素,以便 A[i] == i while N-1

第三个循环打印数组的索引 我 未被值占用的 我 -这意味着 我

不确定,如果这是最有效的解决方案,但我会循环所有条目,并使用位集记住设置了哪些数字,然后测试0位。

我喜欢简单的解决方案,我甚至相信,它可能比计算和,或平方和等更快。

Σ(n^2) 与我们计算的过程相同 Σ(n) 会提供足够的信息来得到两个丢失的号码,是吗 Σ(n^3) 如果有三个也一样,以此类推。

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

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

储存:

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 \Theta(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个条目,n前面的数字

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)) 该算法更直观,具有相同的时间复杂度,占用空间少。

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

在我看来,面试官是在问你怎么做 打印输出 在O(k)时间内而不是在O(N)时间内的最终集合的内容。显然,设置了位之后,您必须遍历所有N位,以确定是否应该打印数字。但是,如果您更改集合的实现方式,则可以在k次迭代中打印出数字。这是通过将数字放入一个对象来实现的,该对象将同时存储在哈希集和双链表中。从哈希集中删除对象时,也会从列表中删除它。答案将留在现在长度为k的列表中。

quickselect 平均来说 O(n) 如果分区是在适当的位置进行的,则使用常量内存。

1. 根据随机轴划分集合 p 分成若干分区 l r ,其中包含大于轴的数字。

2. 通过比较pivot值和每个分区的大小来确定丢失的2个数字所在的分区( p - 1 - count(l) = count of missing numbers in l 和 n - count(r) - p = count of missing numbers in r

3. a) 如果每个分区缺少一个数字,则使用求和差方法查找每个缺少的数字。

   (1 + 2 + ... + (p-1)) - sum(l) = missing #1 和 ((p+1) + (p+2) ... + n) - sum(r) = missing #2

   b) 如果一个分区同时缺少两个数字,并且该分区为空,则缺少的数字为 (p-1,p-2) 或 (p+1,p+2)

   如果一个分区缺少2个数字但不是空的,则递归到该分区。

由于只缺少2个数字,该算法总是丢弃至少一个分区,因此它保留了 quickselect的平均时间复杂度。类似地,对于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

这是一个使用k位额外存储的解决方案,没有任何巧妙的技巧,只是简单明了。执行时间O(n),额外空间O(k)。只是为了证明这个问题可以解决,而不必先阅读解决方案,也不必成为天才:

void puzzle (int* data, int n, bool* extra, int k)
{
    // data contains n distinct numbers from 1 to n + k, extra provides
    // space for k extra bits. 

    // Rearrange the array so there are (even) even numbers at the start
    // and (odd) odd numbers at the end.
    int even = 0, odd = 0;
    while (even + odd < n)
    {
        if (data [even] % 2 == 0) ++even;
        else if (data [n - 1 - odd] % 2 == 1) ++odd;
        else { int tmp = data [even]; data [even] = data [n - 1 - odd]; 
               data [n - 1 - odd] = tmp; ++even; ++odd; }
    }

    // Erase the lowest bits of all numbers and set the extra bits to 0.
    for (int i = even; i < n; ++i) data [i] -= 1;
    for (int i = 0; i < k; ++i) extra [i] = false;

    // Set a bit for every number that is present
    for (int i = 0; i < n; ++i)
    {
        int tmp = data [i];
        tmp -= (tmp % 2);
        if (i >= even) ++tmp;
        if (tmp <= n) data [tmp - 1] += 1; else extra [tmp - n - 1] = true;
    }

    // Print out the missing ones
    for (int i = 1; i <= n; ++i)
        if (data [i - 1] % 2 == 0) printf ("Number %d is missing\n", i);
    for (int i = n + 1; i <= n + k; ++i)
        if (! extra [i - n - 1]) printf ("Number %d is missing\n", i);

    // Restore the lowest bits again.
    for (int i = 0; i < n; ++i) {
        if (i < even) { if (data [i] % 2 != 0) data [i] -= 1; }
        else { if (data [i] % 2 == 0) data [i] += 1; }
    }
}

Q2的一个非常简单的解决方案,我很惊讶没有人回答。使用Q1中的方法求两个缺失数字的和。让我们用s来表示它,那么一个缺失的数字小于s/2,另一个大于s/2(duh)。将从1到S/2的所有数字相加,并将其与公式的结果(类似于Q1中的方法)进行比较,找出缺失数字之间的较低值。从S中减去它就可以找到较大的缺失数。

对于Q2,这是一个比其他解决方案效率稍低的解决方案,但仍然有O(N)个运行时,占用O(k)个空间。

其思想是运行原始算法两次。在第一个例子中,你得到一个缺失的总数,它给出了缺失数的上界。我们打这个号码吧 N 不 ,因此第一个数字只能在间隔中 [1, floor((N-1)/2)] [floor(N/2)+1,N-1]

因此,您将再次循环所有数字,丢弃第一个间隔中未包含的所有数字。那些是的,你记录他们的总数。最后,您将知道丢失的两个数字中的一个,并扩展到第二个。

我有一种感觉,这种方法可以推广,也许在输入的一次传递过程中,多个搜索可以“并行”运行,但我还没有弄清楚怎么做。

1. 前100个整数的预计算异或(val=1^2^3^4….100)
2. 对来自输入流的元素进行异或运算(val1=val1^next\u input)
3. 最终答案=val^val1

def GetValue(A)
  val=0
  for i=1 to 100
    do
      val=val^i
    done
  for value in A:
    do
      val=val^value 
    done
  return val

这个算法实际上可以扩展为两个缺失的数字。第一步不变。当我们用两个缺失的数字调用GetValue时,结果将是 a1^a2 是两个缺失的数字。让我们说

val = a1^a2

现在要从val中筛选出a1和a2,我们取val中的任意一个位 ith 位是在val中设置的。这意味着a1和a2的奇偶校验不同 钻头位置。 现在我们对原始数组进行另一次迭代,并保留两个xor值。一个用于设置第i位的数字,另一个不设置第i位的数字。我们现在有两个数字桶,它保证 a1 and a2 会躺在不同的桶里。现在重复同样的步骤,在每个桶上找到一个丢失的元素。

你能检查一下每个号码是否都存在吗?如果是,您可以尝试以下方法:

S=袋子中所有数字的总和(S<5050)

如果丢失的数字是 x y 然后:

最大值(x)=Z-1

所以你检查一下 1 max(x)

如果你有两个列表的总和和两个列表的乘积,你可以解Q2。

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

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

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

我不知道sqrt,reduce和sum函数的复杂度,所以我无法计算出这个解决方案的复杂度(如果有人知道,请在下面评论)

有一种通用的方法来概括这样的流算法。 我们的想法是使用一些随机化的方法,希望能“传播”这些信息 k 元素转化为独立的子问题,我们原来的算法在这里为我们解决问题。此技术用于稀疏信号重建等。

• 做一个数组, a ,大小 u = k^2 .
• 随便挑一个 universal hash function , h : {1,...,n} -> {1,...,u} . (就像 multiply-shift
• 对于每个 i 在里面 1, ..., n 增加 a[h(i)] += i
• x 在输入流中,减量 a[h(x)] -= x

特定对被发送到同一个bucket的概率小于 1/u 根据通用散列函数的定义。因为有大约 k^2/2 对,我们得到的误差概率最大 k^2/2/u=1/2 . 也就是说,我们成功的概率至少是50%,如果我们增加 u 我们增加了机会。

k^2 logn 一些空间(我们需要 logn 此算法每次更新的时间也恒定,而不是时间

事实上,通过使用注释中描述的技巧,我们甚至可以比幂和方法更有效。

动机

如果要解决一般情况的问题,并且可以存储和编辑数组,那么 Caf's solution 是目前为止效率最高的。如果无法存储阵列(流式版本),则 sdcvvc's answer 是目前唯一建议的解决方案类型。

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

概念

int sum = SumOf(1,n) - SumOf(array)

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

... 它提供了一个边界:在缺失的数字中,肯定有 数字小于或等于 average , 和 大于 平均的 . 这意味着我们可以将每个问题分解为子问题,每个子问题扫描阵列[ O(n)

代码

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 where elements, e:
    // begin <= e < 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 -= 1;
            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 ,因此它仍然是 正常惯例下的空间。

函数调用的数量并不明显 缺少元素,所以我会提供一个视觉效果。您的原始子数组(连接数组)是完整数组,其中包含 k 缺少元素。我们可以想象它们的排列顺序,在哪里 -- 表示连接(同一子数组的一部分):

米 --米 _{2 三} --米 ₄ --(…)--米 _k-1公司 --米

影响 Find

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

所以时间复杂度是 Θ((k-1 + k) * n) = Θ(k*n)

O(log(k)) 空间的复杂性,但如果我们一次只分开一个,它会给我们 .

讨论

O(最小值(k,对数(n))) ,但更难证明。我的直觉是:当有一个异常值时,平均值在分离时表现很差,但是 因为 删除 能够 n .

我认为这不需要任何复杂的数学方程和理论就可以做到。下面是一个就地O(2n)时间复杂度解决方案的建议:

输入表单假设:

#袋数=n

#缺失数=k

包中的数字由长度为n的数组表示

数组中缺少的条目(从包中取出的数字)将替换为数组中第一个元素的值。

如果取4,则4的值将变为2(数组的第一个元素)。

此解决方案的关键是,在遍历数组时,通过对该索引处的值求反来标记已访问号码的索引。

    IEnumerable<int> GetMissingNumbers(int[] arrayOfNumbers)
    {
        List<int> missingNumbers = new List<int>();
        int arrayLength = arrayOfNumbers.Length;

        //First Pass
        for (int i = 0; i < arrayLength; i++)
        {
            int index = Math.Abs(arrayOfNumbers[i]) - 1;
            if (index > -1)
            {
                arrayOfNumbers[index] = Math.Abs(arrayOfNumbers[index]) * -1; //Marking the visited indexes
            }
        }

        //Second Pass to get missing numbers
        for (int i = 0; i < arrayLength; i++)
        {                
            //If this index is unvisited, means this is a missing number
            if (arrayOfNumbers[i] > 0)
            {
                missingNumbers.Add(i + 1);
            }
        }

        return missingNumbers;
    }

这是一个解决方案,它不像sdcvvc/Dimitris Andreou的答案那样依赖于复杂的数学,不像caf和collone Panic那样改变输入数组,不像Chris Lercher、JeremyP和其他许多人那样使用巨大的位集。基本上,我从Svalorzen/Gilad-Deutch的Q2思想开始,将其推广到常见情况Qk,并用Java实现,以证明算法是有效的。

这个主意

假设我们有一个任意的间隔 我 我们只知道它至少包含一个缺失的数字。通过输入数组一次后,只查看 ,我们可以得到 S码 数量呢 问 我 . 我们通过简单的递减来实现 我是 每次我们遇到一个来自 我 (用于获取 问 )通过减少所有数字的预计算和 我 每次遇到的数字(为了获得 ).

和 问 Q=1 ,意思是 我 只包含一个缺失的数字,而这个数字显然 . 我们标记 完成时(在程序中称为“无歧义”),不作进一步考虑。另一方面,如果 ,我们可以计算平均值 A=S/Q 包含在 我 A 至少有一个严格大于 . 现在我们分手了 在里面 A 分成两个较小的间隔,每个间隔至少包含一个缺失的数字。请注意,我们指定的间隔并不重要 A 如果是整数。

S码 和 问 对于每个间隔分别(但在同一过程中),然后用 Q>1 . 我们继续这个过程,直到没有新的“模糊”区间,也就是说,我们没有什么可分割的,因为每个区间正好包含一个缺失的数字(我们总是知道这个数字,因为我们知道 ). 我们从包含所有可能数字(如 在问题中)。

时空复杂性分析

p 我们需要做的是,直到过程停止,永远不超过失踪人数计数 可以得到严格的证明。另一方面,也有一个经验上限 p<日志 ₂ 对于较大的 k . 我们需要对输入数组的每个数字进行二进制搜索,以确定它所属的间隔。这增加了 时间复杂性的乘数。

总的来说,时间复杂度是 O(无)á 最小值(k,对数N)á 对数(k) . 请注意,对于大型 k O(无)á (千)

对于它的工作,算法需要 最多可储存的额外空间 时间间隔,这比 在“位集”解决方案中。

下面是一个实现上述算法的Java类。它总是返回一个 已排序 因为它在第一次通过时就计算出来了。整个数字范围由 minNumber 和 maxNumber

public class MissingNumbers {
    private static class Interval {
        boolean ambiguous = true;
        final int begin;
        int quantity;
        long sum;

        Interval(int begin, int end) { // begin inclusive, end exclusive
            this.begin = begin;
            quantity = end - begin;
            sum = quantity * ((long)end - 1 + begin) / 2;
        }

        void exclude(int x) {
            quantity--;
            sum -= x;
        }
    }

    public static int[] find(int minNumber, int maxNumber, NumberBag inputBag) {
        Interval full = new Interval(minNumber, ++maxNumber);
        for (inputBag.startOver(); inputBag.hasNext();)
            full.exclude(inputBag.next());
        int missingCount = full.quantity;
        if (missingCount == 0)
            return new int[0];
        Interval[] intervals = new Interval[missingCount];
        intervals[0] = full;
        int[] dividers = new int[missingCount];
        dividers[0] = minNumber;
        int intervalCount = 1;
        while (true) {
            int oldCount = intervalCount;
            for (int i = 0; i < oldCount; i++) {
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    if (itv.quantity == 1) // number inside itv uniquely identified
                        itv.ambiguous = false;
                    else
                        intervalCount++; // itv will be split into two intervals
            }
            if (oldCount == intervalCount)
                break;
            int newIndex = intervalCount - 1;
            int end = maxNumber;
            for (int oldIndex = oldCount - 1; oldIndex >= 0; oldIndex--) {
                // newIndex always >= oldIndex
                Interval itv = intervals[oldIndex];
                int begin = itv.begin;
                if (itv.ambiguous) {
                    // split interval itv
                    // use floorDiv instead of / because input numbers can be negative
                    int mean = (int)Math.floorDiv(itv.sum, itv.quantity) + 1;
                    intervals[newIndex--] = new Interval(mean, end);
                    intervals[newIndex--] = new Interval(begin, mean);
                } else
                    intervals[newIndex--] = itv;
                end = begin;
            }
            for (int i = 0; i < intervalCount; i++)
                dividers[i] = intervals[i].begin;
            for (inputBag.startOver(); inputBag.hasNext();) {
                int x = inputBag.next();
                // find the interval to which x belongs
                int i = java.util.Arrays.binarySearch(dividers, 0, intervalCount, x);
                if (i < 0)
                    i = -i - 2;
                Interval itv = intervals[i];
                if (itv.ambiguous)
                    itv.exclude(x);
            }
        }
        assert intervalCount == missingCount;
        for (int i = 0; i < intervalCount; i++)
            dividers[i] = (int)intervals[i].sum;
        return dividers;
    }
}

为了公平起见,这个类以 NumberBag 物体。 不允许对数组进行修改和随机访问,还统计请求数组进行顺序遍历的次数。它也更适合于大阵列测试 Iterable<Integer> int int[] 方便的测试准备。如果需要的话,更换并不难, 数字标签 通过 整数[] 或 键入 find 签名,将其中的两个for循环更改为foreach循环。

import java.util.*;

public abstract class NumberBag {
    private int passCount;

    public void startOver() {
        passCount++;
    }

    public final int getPassCount() {
        return passCount;
    }

    public abstract boolean hasNext();

    public abstract int next();

    // A lightweight version of Iterable<Integer> to avoid boxing of int
    public static NumberBag fromArray(int[] base, int fromIndex, int toIndex) {
        return new NumberBag() {
            int index = toIndex;

            public void startOver() {
                super.startOver();
                index = fromIndex;
            }

            public boolean hasNext() {
                return index < toIndex;
            }

            public int next() {
                if (index >= toIndex)
                    throw new NoSuchElementException();
                return base[index++];
            }
        };
    }

    public static NumberBag fromArray(int[] base) {
        return fromArray(base, 0, base.length);
    }

    public static NumberBag fromIterable(Iterable<Integer> base) {
        return new NumberBag() {
            Iterator<Integer> it;

            public void startOver() {
                super.startOver();
                it = base.iterator();
            }

            public boolean hasNext() {
                return it.hasNext();
            }

            public int next() {
                return it.next();
            }
        };
    }
}

测验

下面给出了演示这些类用法的简单示例。

import java.util.*;

public class SimpleTest {
    public static void main(String[] args) {
        int[] input = { 7, 1, 4, 9, 6, 2 };
        NumberBag bag = NumberBag.fromArray(input);
        int[] output = MissingNumbers.find(1, 10, bag);
        System.out.format("Input: %s%nMissing numbers: %s%nPass count: %d%n",
                Arrays.toString(input), Arrays.toString(output), bag.getPassCount());

        List<Integer> inputList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            inputList.add(2 * i);
        Collections.shuffle(inputList);
        bag = NumberBag.fromIterable(inputList);
        output = MissingNumbers.find(0, 19, bag);
        System.out.format("%nInput: %s%nMissing numbers: %s%nPass count: %d%n",
                inputList, Arrays.toString(output), bag.getPassCount());

        // Sieve of Eratosthenes
        final int MAXN = 1_000;
        List<Integer> nonPrimes = new ArrayList<>();
        nonPrimes.add(1);
        int[] primes;
        int lastPrimeIndex = 0;
        while (true) {
            primes = MissingNumbers.find(1, MAXN, NumberBag.fromIterable(nonPrimes));
            int p = primes[lastPrimeIndex]; // guaranteed to be prime
            int q = p;
            for (int i = lastPrimeIndex++; i < primes.length; i++) {
                q = primes[i]; // not necessarily prime
                int pq = p * q;
                if (pq > MAXN)
                    break;
                nonPrimes.add(pq);
            }
            if (q == p)
                break;
        }
        System.out.format("%nSieve of Eratosthenes. %d primes up to %d found:%n",
                primes.length, MAXN);
        for (int i = 0; i < primes.length; i++)
            System.out.format(" %4d%s", primes[i], (i % 10) < 9 ? "" : "\n");
    }
}

import java.util.*;

public class BatchTest {
    private static final Random rand = new Random();
    public static int MIN_NUMBER = 1;
    private final int minNumber = MIN_NUMBER;
    private final int numberCount;
    private final int[] numbers;
    private int missingCount;
    public long finderTime;

    public BatchTest(int numberCount) {
        this.numberCount = numberCount;
        numbers = new int[numberCount];
        for (int i = 0; i < numberCount; i++)
            numbers[i] = minNumber + i;
    }

    private int passBound() {
        int mBound = missingCount > 0 ? missingCount : 1;
        int nBound = 34 - Integer.numberOfLeadingZeros(numberCount - 1); // ceil(log_2(numberCount)) + 2
        return Math.min(mBound, nBound);
    }

    private void error(String cause) {
        throw new RuntimeException("Error on '" + missingCount + " from " + numberCount + "' test, " + cause);
    }

    // returns the number of times the input array was traversed in this test
    public int makeTest(int missingCount) {
        this.missingCount = missingCount;
        // numbers array is reused when numberCount stays the same,
        // just Fisher–Yates shuffle it for each test
        for (int i = numberCount - 1; i > 0; i--) {
            int j = rand.nextInt(i + 1);
            if (i != j) {
                int t = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = t;
            }
        }
        final int bagSize = numberCount - missingCount;
        NumberBag inputBag = NumberBag.fromArray(numbers, 0, bagSize);
        finderTime -= System.nanoTime();
        int[] found = MissingNumbers.find(minNumber, minNumber + numberCount - 1, inputBag);
        finderTime += System.nanoTime();
        if (inputBag.getPassCount() > passBound())
            error("too many passes (" + inputBag.getPassCount() + " while only " + passBound() + " allowed)");
        if (found.length != missingCount)
            error("wrong result length");
        int j = bagSize; // "missing" part beginning in numbers
        Arrays.sort(numbers, bagSize, numberCount);
        for (int i = 0; i < missingCount; i++)
            if (found[i] != numbers[j++])
                error("wrong result array, " + i + "-th element differs");
        return inputBag.getPassCount();
    }

    public static void strideCheck(int numberCount, int minMissing, int maxMissing, int step, int repeats) {
        BatchTest t = new BatchTest(numberCount);
        System.out.println("╠═══════════════════════╬═════════════════╬═════════════════╣");
        for (int missingCount = minMissing; missingCount <= maxMissing; missingCount += step) {
            int minPass = Integer.MAX_VALUE;
            int passSum = 0;
            int maxPass = 0;
            t.finderTime = 0;
            for (int j = 1; j <= repeats; j++) {
                int pCount = t.makeTest(missingCount);
                if (pCount < minPass)
                    minPass = pCount;
                passSum += pCount;
                if (pCount > maxPass)
                    maxPass = pCount;
            }
            System.out.format("║ %9d  %9d  ║  %2d  %5.2f  %2d  ║  %11.3f    ║%n", missingCount, numberCount, minPass,
                    (double)passSum / repeats, maxPass, t.finderTime * 1e-6 / repeats);
        }
    }

    public static void main(String[] args) {
        System.out.println("╔═══════════════════════╦═════════════════╦═════════════════╗");
        System.out.println("║      Number count     ║      Passes     ║  Average time   ║");
        System.out.println("║   missimg     total   ║  min  avg   max ║ per search (ms) ║");
        long time = System.nanoTime();
        strideCheck(100, 0, 100, 1, 20_000);
        strideCheck(100_000, 2, 99_998, 1_282, 15);
        MIN_NUMBER = -2_000_000_000;
        strideCheck(300_000_000, 1, 10, 1, 1);
        time = System.nanoTime() - time;
        System.out.println("╚═══════════════════════╩═════════════════╩═════════════════╝");
        System.out.format("%nSuccess. Total time: %.2f s.%n", time * 1e-9);
    }
}

Try them out on Ideone

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

对于任意k,这里有一个简单的解决方案:对于一组数字中的每一个v,累加2^v的和。最后,循环i从1到N。如果与2^i按位AND的和为零,则缺少i(或者在数字上,如果总和除以2^i的下限是偶数。或者 sum modulo 2^(i+1)) < 2^i

很简单,对吧?O(N)时间,O(1)存储,支持任意k。

所以你可以很聪明的计算和,平方和,立方和。。。求出v^k的和,然后做一些复杂的数学运算来提取结果。但这些数字也很大,这就引出了一个问题:我们谈论的是什么抽象的运作模式?在O(1)空间中有多少是合适的,以及需要多长时间来计算出所需大小的数字?

很好的问题。我会用一组差来表示Qk。很多编程语言甚至都支持它,比如在Ruby中:

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

你可以试着用 Bloom Filter

n 信息和需要知道 k n-k O(log k+1) . 之后,集合包含 缺少元素,没有其他处理要做。

这当然不是批处理预生成的数字包的最快方法,因为整个过程都在运行 O((log 1 + log 2 + ... + log n) + (log n + log n-1 + ... + log k)) . 但它对任何价值 k (即使事先不知道)在上面的例子中,它是以一种最小化最关键间隔的方式应用的。

你可以从对称性(数学语言中的组)的角度来考虑解决方案。不管这组数字的顺序如何,答案应该是一样的。如果你要用 k 函数来帮助确定缺少的元素,您应该考虑哪些函数具有该属性:symmetric。函数 s_1(x) = x_1 + x_2 + ... + x_n 是对称函数的一个例子,但也有更高阶的例子。尤其要考虑 初等对称函数 . 二次初等对称函数是 s_2(x) = x_1 x_2 + x_1 x_3 + ... + x_1 x_n + x_2 x_3 + ... + x_(n-1) x_n

你可以在构建初等对称函数的时候注意 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) . 它的计算结果是 0 如果你输入任何一个数字 x_i . 展开多项式,得到 z^n-s_1(x)z^(n-1)+ ... + (-1)^n s_n . 初等对称函数也出现在这里,这并不奇怪,因为如果我们对根应用任何置换,多项式应该保持不变。

所以我们可以建立多项式,并尝试将其因子化,以找出哪些数字不在集合中,正如其他人所提到的。

最后,如果我们关心大量内存溢出(n次对称多项式的阶数 100! mod p 哪里 p 然后又发现 当输入是集合中的一个数字时,当输入是不在集合中的数字时,它的计算结果为非零值。然而,正如其他人所指出的,从多项式中求出值的时间取决于 k ,不是 N ,我们必须考虑多项式 模块p

另一种方法是使用残差图过滤。

假设我们有1到4个数字,3不见了。二进制表示如下:,

1=001b,2=010b,3=011b,4=100b

我可以创建如下流图。

                   1
             1 -------------> 1
             |                | 
      2      |     1          |
0 ---------> 1 ----------> 0  |
|                          |  |
|     1            1       |  |
0 ---------> 0 ----------> 0  |
             |                |
      1      |      1         |
1 ---------> 0 -------------> 1

请注意,流图包含x个节点,而x是位数。最大边数为(2*x)-2。

所以对于32位整数,需要O(32)空间或O(1)空间。

如果从1,2,4开始去掉每个数的容量,剩下的就是残差图。

0 ----------> 1 ---------> 1

最后我将运行如下循环,

 result = []
 for x in range(1,n):
     exists_path_in_residual_graph(x)
     result.append(x)

现在结果出来了 result 也包含未丢失的数字(假阳性)。但是 如果有 k 缺少元素。

我将把所给的单子再看一遍,以标明结果是否遗漏。

最后,通过获取节点可以减少误报的数量(以及所需的空间) 00 , 01 11 , 10 而不仅仅是 0 和 1 .

为了使解释更简单,假设我得到了从1到15的数字,其中有两个丢失了,即9和14,但我不知道。让包看起来像这样:

我们知道每个数字在内部是以位的形式表示的。 对于16之前的数字,我们只需要4位。对于10^9之前的数字,我们需要32位。但是让我们关注4位,然后我们可以推广它。

0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

但现在我们少了两个数字。因此,我们的表示将如下所示(显示顺序是为了理解,但可以是任何顺序):

(2MSD|2LSD)
00|01
00|10
00|11
-----
01|00
01|01
01|10
01|11
-----
10|00
missing=(10|01) 
10|10
10|11
-----
11|00
11|01
missing=(11|10)
11|11

= [__,__,__,__] 
   00,01,10,11

从左到右扫描袋子,填充上面的数组,使每个位数组的bin包含数字的计数。结果如下:

= [ 3, 4, 3, 3] 
   00,01,10,11

= [ 3, 4, 4, 4] 
   00,01,10,11

因此,我们知道有两个数字丢失:一个最2个有效位是10,另一个最2个有效位是11。现在再次扫描列表,并填写一个大小为2的位数组,以获得下面的2个有效数字。这一次,只考虑最2位有效数字为10的元素。我们将使用位数组:

= [ 1, 0, 1, 1] 
   00,01,10,11

= [ 1, 0, 1, 1]
00,01,10,11

因此,我们可以在一个恒定的空间中找到丢失的数字。我们可以把它推广到100,1000,10^9或任何一组数字。

参考文献:中的问题1.6 http://users.ece.utexas.edu/~adnan/afi-samples-new.pdf

我相信我有一个 O(k) 时间和 O(log(k)) floor(x) 和 log2(x)

你有一个 k -位长整数(因此 log8(k) 空格)添加 x^2 s=1^2+2^2+... 这需要 O(N) 时间(这对面试官来说不是问题)。最后你得到 j=floor(log2(s)) 哪个是你要找的最大的号码。那么 s=s-j 你再做一次上面的:

for (i = 0 ; i < k ; i++)
{
  j = floor(log2(s));
  missing[i] = j;
  s -= j;
}

2756 -位整数,而不是双精度。所以呢?简单地说,对于每2个字节(或1、或3、或4),您可以使用这些函数来获得所需的数字,但这会增加一个

试着找出1到50之间的乘积:

当你把数字一个接一个地取出来时,把它们相乘,得到乘积P2。但此处缺少两个数字,因此P2<第1页。

两个错误项的乘积,a x b=P1-P2。

你已经知道总和了,a+b=S1。

这听起来可能很愚蠢,但是,在第一个问题中,你必须看到包中所有剩余的数字,才能用这个等式把它们加起来找到丢失的数字。

所以,既然你能看到所有的数字,就去寻找丢失的数字。当两个数字丢失时也是如此。我觉得很简单。当你看到袋子里剩下的数字时,用公式是没有意义的。