找数字

找一个数字

题目描述:从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一定属于150或51100两个区间。如果n属于前一个区间,那么n也一定属于125或2650两个区间。这个过程可以一直划分,直到找到这个数字。

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

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

  1. 初始化查找区间$[p,q]$,一开始就是$[1,100]$;
  2. 选择该区间的中值k,将集合中所有小于等于k的数字和大于k的数字分开,最后获得两个子集合$[p,k]$和$[k+1,q]$;当然在做划分的时候可以顺带统计元素个数了;
  3. 如果小于等于k的元素集合数量不足,那么缺失的数字就包含于区间$[p,k]$,否则就在另一个区间;
  4. 经过步骤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的值可以任意更换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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)$

更多数字?

如果现在问题变成了:从1-100中删去任意n个数字,然后将剩下的100-n个数字打乱,得到无序序列$a_1,a_2,…,a_{100-n}$。现在需要用一种方法找到这n个数字。

桶排序

依然可用。

分治法

可以使用,但是当n较大的时候,实际上就退化成对数字排序的问题。花在递归函数调用上的时间影响较大。

异或

策略是不断使用比特的特征将找n个数的问题转化为找n-1个数的问题。只不过重复循环的时间复杂度就比较高。