Sta*_*ilo 2 c arrays algorithm
有一个整数数组,长度为n.在他的一半以上的元素中,有一个k未知的常数.你不能改变阵列(他是read-only),你只有一个O(1)大小的记忆.你需要找到k最好的复杂性(你认为你可以低于O(n)？)
例:
{1, 6, 44, 1, 1, 8, 1} so k = 1
我想到了中位数,但是我不允许改变数组......
谢谢
我相信这就是你要找的东西:http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html
基本上,您迭代并维护两个数据:候选和投票计数.每个元素增加或减少投票计数,具体取决于元素本身是否与候选者匹配.如果投票为0,则元素本身成为候选者.
只要存在多数,在迭代过程结束时,当前候选者将成为多数元素.