两个有趣的小题目

@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)\) 。