找数字

发表于 2019-07-19 更新于 2019-08-06

找一个数字

题目描述：从1-100中删去任意一个数字，然后将剩下的99个数字打乱，得到无序序列$a_1,a_2,…,a_{99}$。现在需要用一种方法找到这个数字。

加法

这是最简单的方法，将所有的数字求和$S_1 = \sum_{i=1}^{99}{a_i}$，然后用$S_2 = \sum_{i=1}^{100}{i}=5050$减去$S_1$就获得答案。

复杂度分析：
如果不算上保存99个数的空间，那么该方法只需要$O(1)$的空间记录求和，以及$O(n)$的时间遍历序列。

桶排序

另外一个容易想到的的方法，由于数字连续并且数据规模小，所以只需要构建100个“桶”。从头遍历给定的99个数字，将其放入数值对应的“桶”中。最后从头开始找这100个“桶”，哪个桶空就说明缺少了哪个数字。

复杂度分析：
该方法需要用到$O(n)$的额外空间，以及$O(n)$的时间复杂度。

异或

对于任意整数n，有$n \land n = 0$，根据这个性质，就可以预先将1-100所有的整数异或，得到“异或和”X，然后再将X和序列中的每一个元素异或，最后得到的答案就是被抠掉的数字。

复杂度分析：
和做加法类似，时间复杂度为$O(n)$，空间复杂度为$O(1)$，不过使用异或方法不需要考虑溢出的情况。

分治法

假设被抠掉的数字是n，那么n一定属于1~~50或51~~100两个区间。如果n属于前一个区间，那么n也一定属于1~~25或26~~50两个区间。这个过程可以一直划分，直到找到这个数字。

现在需要确定这个数字是多少，那么还是类似的思想。如果被抠掉的数字属于1~~50，那么小于等于50的数字只有49个。现在数一数$a_i$有多少个落入1~~50区间，不妨假设只有49，那么又可以继续划分为计算1~25中有多少个数字的问题。这个过程可以一直划分，直到找到这个数字。

上面这个过程耗时最大的步骤就是统计区间的元素个数。一遍一遍扫描肯定是不够好的，可以参考快速排序的元素划分方式。

初始化查找区间$[p,q]$，一开始就是$[1,100]$；
选择该区间的中值k，将集合中所有小于等于k的数字和大于k的数字分开，最后获得两个子集合$[p,k]$和$[k+1,q]$；当然在做划分的时候可以顺带统计元素个数了；
如果小于等于k的元素集合数量不足，那么缺失的数字就包含于区间$[p,k]$，否则就在另一个区间；
经过步骤2、3就缩小了查找区间为原来的一半，对该区间重复步骤2、3，直到区间中只剩下一个元素，而区间对应的集合为空的元素就是缺失的数字。

每次搜索的区间都会缩小一半，因此只需要经过$O(log(n))$步就可以找到缺少的元素。具体计算如下。用$T(n)$表示父查询任务的时间复杂度，则有$T(n) = T(n/2) + f(n)$，当$n = 1$时，$T(n) = f(1)$；$f(n)$的时间复杂度为$O(n)$。

$$
\begin{aligned}
T(n) &= T(n/2) + f(n) \
&= T(n/4) + 2f(n) + f(n) \
&= \dots \
&= T(1) + f(n)\sum_{i=0}^{k-1}{2^i} \
&= T(1) + (2^k - 1)f(n) \
&= O(n)
\end{aligned}
$$

复杂度分析：
已经证明时间复杂度为$O(n)$。空间复杂度$O(n)$。

找两个数字

题目描述：从1-100中删去任意两个数字，然后将剩下的98个数字打乱，得到无序序列$a_1,a_2,…,a_{98}$。现在需要用一种方法找到这两个数字。

桶排序

这个方法哪怕n为其他值也是可以使用的，十分简单不再赘述。

方程组

此时简单的差值求解不奏效了，只能求解得到两个数字的和。如果需要解出这两个数字，那就需要用一个等式构成方程组。

能否使用异或的方式获取一个等式构成方程组呢？即解方程组
$$
\begin{cases}
x + y = m \
x \land y = n
\end{cases}
$$

要判断是否可行，可以列一下真值表：

$x_i$	$y_i$	+	$\land$
0	0	0	0
0	1	1	1
1	0	1	1
1	1	0	0

暂时先不考虑进位对结果的影响，也就是最低位的情况。显然最低位已经无法根据加法值和异或值确定结果了（第2、3行），所以这个方法是不行的。

而如果使用方程组
$$
\begin{cases}
x + y = m \
x \times y = n
\end{cases}
$$

虽然理论可行，但是计算$100!$在程序上会导致溢出。

如果改用对数方程是否可行？
$$
\begin{cases}
x + y = m \
log(x) + log(y) = n
\end{cases}
$$

虽然可能存在精度的问题，但是还是决定实验一下。代码如下，x和y的值可以任意更换。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int x = 1, y = 2;
    int sum1 = 5050, sum2 = 0.0;
    double logsum1 = 0, logsum2 = 0.0;

    for (int i = 1; i <= 100; ++i) {
        logsum1 += log(i);
    }
    for (int i = 1; i <= 100; ++i) {
        if (i == x || i == y) continue;
        logsum2 += log(i);
        sum2 += i;
    }

    double x_plus_y = sum1 - sum2;
    double x_mult_y = exp(logsum1 - logsum2);

    cout << "x + y = " << x_plus_y << endl;
    cout << "x * y = " << x_mult_y << endl;
    return 0;
}

经过测验，对于上面的代码，使用double型变量可以提供足够的精度，一方面是double有52bits的有效数据位，足够精细，另一方面是由于100以内数的对数值并不会相差很大，所以浮点数相加并不会丢失很多精度。同样的代码如果使用float存储浮点结果，就会出现精度丢失的问题。

分治

分治法还是可以用来解决这个问题。还是用之前的假设：查询区间为$[p,q]$，中值为k，左查询区间为$[p,k]$，右查询区间为$[k+1,q]$。

无论缺失的两个数字取自哪个子查询区间，区间对应元素集合就会缺少数字，那么就将父查询任务转化为有数字缺少的区间的子查询任务。最差情况下，缺失的两个数字分别属于两个子查询区间。

借鉴“找一个数字”中分治法的符号表示，有$T(n) \le 2T(n/2) + f(n)$，当$n = 1$时，$T(n) = f(1)$；$f(n)$的时间复杂度为$O(n)$。

求解递推式：
$$
\begin{aligned}
T(n) &\le 2T(n/2) + f(n) \
&= 2^2T(n/4) + 2f(n) + f(n) \
&= \dots \
&= 2^kT(1) + f(n)\sum_{i=0}^{k-1}{2^i} \
&= 2^kT(1) + (2^k - 1)f(n) \
&= O(n)
\end{aligned}
$$

复杂度分析：
$T(n/2) + f(n) \le T(n) \le 2T(n/2) + f(n)$，因此找两个数字的时间复杂度为$O(n)$；空间复杂度还是$O(n)$

异或

虽然加法方程和异或方程联立无法解得结果，但是异或结果还是说明了x和y数位上的特点。

从异或结果中看看从1-8中抠掉2个数字，求抠掉的两个数字。

十进制	二进制
1	0001
2	0010
3（抠掉）	0011
4	0100
5	0101
6（抠掉）	0110
7	0111
8	1000

令x=3，y=6，则异或结果为0101，表明第1位（从低到高）和第3位不一样。如果按照第1位是否1将原来的数字分成两组，实际上就是将找两个数的问题转化为找1个数的问题。

复杂度分析
和找1数字的时候一样，时间复杂度为$O(n)$，空间复杂度为$O(1)$

找一个数字

加法

桶排序

异或

分治法

找两个数字

桶排序

方程组

分治

异或

更多数字？

桶排序

分治法

异或