0%

两个有趣的小题目

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