c - 查找出现在数组一半以上元素中的常量

Question

有一个整数数组，他的长度为n。他一半以上的元素都有一个常数 k这是未知的。 你不能改变数组(他是 read-only )，你只有 O(1) 的内存。尺寸。 您需要找到k最佳复杂度(你认为你可以得到低于 O(n) ？)

示例:

{1, 6, 44, 1, 1, 8, 1} so k = 1

我考虑过使用中位数，但不允许我更改数组...

谢谢

Answer 1

我相信这就是您正在寻找的:http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html

本质上，您迭代并维护两个数据:候选人和选票计数。每个元素都会增加或减少投票数，具体取决于元素本身是否与候选人匹配。如果投票为 0，则该元素本身成为候选者。

只要有多数存在，在迭代过程结束时，当前候选元素将是该多数元素。