@ehk 给了我两个很有趣的题目，感觉很不错哦。

Problem

出现次数最多的数

给定一个大小为 $n+1$ 的数组，每个元素都是 $[1, n]$ 里面的整数，且只有一个数出现两次或以上，不一定所有的数都出现过。要求在 $O(n)$ 时间 $O(1)$ 空间内找出这个数，且不允许修改数组。

Peak

给定一个二维矩阵 $A_{n \times m}$ ，保证：

1. $n, m \geq 3$；
2. 每个元素均不相同；
3. 对于 $1 \leq i \leq n$ ，$A_{i, 1} < A_{i, 2}, A_{i, m - 1} > A_{m,i }$
4. 对于 $1 \leq j \leq m$ ，$A_{1,j} < A_{2, j}, A_{n-1,j} > A_{n,j}$

求一个点的坐标 $(x, y)$，使得 $A_{x,y} > \max(A_{x - 1, y}, A_{x + 1, y}, A_{x, y - 1}, A_{x, y + 1})$ 。

要求时间复杂度 $O(n+m)$ 空间复杂度 $O(1)$ ，可以认为 $A$ 是 black-box 访问。

Solution

出现次数最多的数

令 $x$ 为原数组，考虑一个 $n$ 条边的图 $G$ ，其中 $i \to x[i]$。则在这个图中只有一个点入度大于 1 。

由图论知识知，$G$ 由若干个连通分量，其中有且仅有一个连通分量为 $\rho$ 型，其余全部为一个环，而我们的目标就是找到 $\rho$ 型分量中的那个入口。

注意到 $n + 1$ 没有入度，故 $n+1$ 一定在 $\rho$ 分量上，且不在这个分量的环上。我们可以模仿 Pollard-rho 算法，用两个指针 $p, q$，初始值均为 $n+1$ ，然后 $p \gets x[p], q \gets x[x[q]]$，即每次 $p$ 跳一步，$q$ 跳两步，最后 $p = q$ 时即为答案。

Extension

其实这个题可以有好多种不同的限制，可以得到很多不同的题目：

1. 只有一个数出现两次，其余数只出现一次；
2. 允许修改数组，$O(n \log n)$ 时间，$O(1)$ 空间；
3. 不允许修改数组，$O(n \log n)$ 时间，$O(1)$ 空间；

Peak

首先我们有一个 naive 的做法：随机找一个点，然后每次找周围一个比其大的点走过去，直到走不动为止。

但是……这个算法是可以是被卡到 $\Omega(nm)$ 的。反例很容易构造就不举了。

我们考虑在此基础上设计一个递归算法，每次选择一行，然后把行数折半，选择一边递归下去。为了保证在保留的一半中一定存在答案，我们需要确定：按照以前这个游走算法，最后一定不会跨过我们选择的这一行。于是一个机智的想法就是：我们看找的这一行的最大值是不是一个 peak。如果不是则我们可以选择一边继续递归，否则返回答案。由于游走的过程中，答案会不断增加，因此如果当前行最大值都不是 peak 了，继续游走下去肯定不会跨过这一行。

于是这样我们就有了一个 $O(m \log n)$ 的算法了。再稍稍优化一下就可以做到 $O(n + m)$ 。注意到每次我们是以 $O(m)$ 的代价把行数变成原来的一半。我们还可以对列也进行同样的操作：以 $O(n)$ 的代价把列数变成原来的一半。于是新算法为：行和列交替进行，每次去除一半的行或一半的列。这样第一次对行的操作时间复杂度为 $n$ 第二次为 $\frac{1}{2} n$ 第三次为 $\frac{1}{4} n$ 总时间复杂度为 $O(n)$，对列的也一样，为 $O(m)$ ，故总时间为 $O(n+m)$ 。