performance - 查找是否有元素重复自身 n/k 次

Question

你有一个数组大小 n 和一个常量 k(随便)

你可以假设数组是 int 类型(尽管它可以是任何类型)

描述一种算法，该算法查找是否有一个元素自身重复至少 n/k 次...如果有则返回一个。在线性时间内这样做 (O(n))

要点:使用常量内存执行此算法(甚至伪代码)并仅在数组上运行两次

Answer 1

我不是 100% 确定，但听起来您想解决 the Britney Spears problem —使用常量内存查找构成样本特定部分的项目。

这里是问题的英文陈述，以及解决方案的草图:

… from a 2002 article by Erik D. Demaine of MIT and Alejandro López-Ortiz and J. Ian Munro of the University of Waterloo in Canada. Demaine and his colleagues have extended the algorithm to cover a more-general problem: Given a stream of length n, identify a set of size m that includes all the elements occurring with a frequency greater than n /( m +1). (In the case of m =1, this reduces to the majority problem.) The extended algorithm requires m registers for the candidate elements as well as m counters. The basic scheme of operation is analogous to that of the majority algorithm. When a stream ele­ment matches one of the candidates, the corresponding counter is incremented; when there is no match to any candidate, all of the counters are decremented; if a counter is at 0, the associated candidate is replaced by a new element from the stream.