4

设计和分析一个线性时间算法，以确定在 n 个元素的列表中是否存在一个在列表中至少重复 n/10 次的元素。

我怎样才能做到这一点？我发布我自己的想法作为答案。

4

3 回答 3

12

我认为这些元素是可比较的。

执行以下选择算法：n/10th、2n/10th、...、9n/10th、10(n/10)th 最小元素1

这些是你的候选人。检查每个问题的#occurrences，如果其中一个重复至少 n/10 次，则答案是true。否则，它是false。

证明：
如果一个元素至少出现 n/10 次，那么它必须与k*n/10for some k(在排序列表中) 2 “相交” 。因此，该元素将被选为“候选者”，稍后您将准确地发现（通过计算）它出现了多少次，并将返回true。

如果没有元素重复n/10多次，则算法将false在检查每个候选者的最后一步中轻松返回。

复杂度：
每个选择算法都是O(n)，做 10 次。此外，对于每个候选人，都需要对列表进行线性扫描，这也是总体上的O(n)总计O(n)——但常数很糟糕。

说明：

(1) 选择算法会在一个有序列表中找到索引n/10, 2n/10,...9n/10 中的元素，而算法本身只是O(n)

（2）我们看一下[1,2,..,100,100,..,100]（11乘以100）的例子。
请注意，列表已排序，元素 100 出现在：list[9*n/10](index 9*n/10) 中。选择算法的思想是——即使你打乱列表select(list,9*n/10)——总是会返回相同的元素——在本例中为 100——因为它是9n/10排序列表中的第 th 个元素（这就是算法所做的）。

e现在，您可以看到对于重复次数的每个元素（让它成为） n/10，都有一些索引i，使得在列表的排序版本中，索引中的所有元素都i,i+1,...,i+n/10将是e。这些指数之一必须是k*n/10某些指数之一k（说服自己为什么！）。因此，选择算法k*n/10将产生e。

于 2012-11-24T15:59:01.087 回答
3

让我告诉你一个聪明的单通算法来找到一个多数元素（一个频率高于 n/2 的元素），你应该看看如何适应它：

best = null
count = 0

foreach x in list:
   if (count == 0)
      count++
      best = x
   else if (best == x)
      count++
   else
      count--

return best

如果存在多数元素，则上述算法将找到它（一次通过，恒定空间）。一旦你弄清楚它是如何工作的，你就会看到它如何适应 n/10 的情况。

于 2012-11-24T16:51:30.673 回答
0

我的解决方案是将列表分成 10/n 个组，每个组包含 10 个元素，然后对每个组执行随机选择排序，这将花费 O(1)*O(n) 时间，即 O(n ）。

由于要满足要求，候选元素必须在 n/10 组中的每一个中显示，我们可以对第一组中的 10 个元素中的每一个执行扫描，这将花费 10*O(n) 时间。

所以算法的总时间是O(n)+10*O(n)，还是O(n)。

但是，如果组中的元素如下所示，这将不起作用：

1,2,3,4,5,6,7,8,9,10
11,11,11,11,11,11,11,11,11,11
...
11,11,11,11,11,11,11,11,11,11

我的算法将返回不存在这样11的元素，而实际上是出现超过 n/10 次的元素。

于 2012-11-24T15:52:53.783 回答