查找是否有一个元素重复n/k次

你有一个数组大小n and a constant k（任何）

您可以假设数组是 int 类型（尽管它可以是任何类型）

描述一种算法，用于查找是否存在至少重复自身的元素n/k次...如果有返回一次。在线性时间内执行此操作（O(n))

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

我不是 100% 确定，但听起来你想解决布兰妮·斯皮尔斯问题 http://www.americanscientist.org/issues/pub/the-britney-spears-problem—使用常量内存查找构成样本特定部分的项目。

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

…摘自 Erik 2002 年的一篇文章 麻省理工学院的 D. Demaine 和 Alejandro López-Ortiz 和 J. Ian Munro 加拿大滑铁卢大学。 德曼和他的同事们 扩展算法以覆盖 更一般的问题：给定一个流 长度为 n，确定一组大小为 m 包括所有元素 发生频率更大 比 n /( m +1) 。 （当m=1时， 这减少了多数问题。） 扩展算法需要 m 注册候选元素 以及 m 计数器。基础的 操作方案类似于 多数算法。当一个 流元素匹配其中之一 候选人，相应的柜台 是递增的；当没有匹配的时候 对于任何候选人，所有柜台 递减；如果计数器为 0， 相关候选人被替换 通过流中的新元素。