arrays - 查找数组中的元素是否比某个值出现得更频繁

Question

我有一个问题，给定一个数组，A[1...n] 的 n 个(不一定不同)整数，找到一个算法来确定是否有任何项目在 A 中出现超过 n/4 次的上限。

看起来最好可能的最坏情况时间是 O(n)。我知道多数元素算法，想知道这是否适用于这种情况。如果您对解决此问题有任何建议，请告诉我。

Answer 1

这只是算法的一个想法，但我相信它应该可以实现。

主要技巧如下。如果你观察任何四种元素，发现它们都不一样，你可能会把这四种元素都扔掉。 (如果任何抛出的元素在旧数组中的频率超过 1/4，它将在新数组中；如果没有，则没有)。

因此，您遍历一个数组，丢弃四元组，然后重新排列其余部分。例如，如果您有 AABC，然后是 DDEF，您可以重新排列为 AADDBCEF 并丢弃 BCEF。我会让你弄清楚细节，这并不难。最后你应该留下成对的相同元素。然后你扔掉奇数元素并重复。

每次运行后，您可能会剩下 1、2 或 3 个元素，没有一对是您不能丢弃的。不用担心，您可以合并两次运行的剩余元素，使得剩余堆中的元素永远不会超过 3 个。例如。如果在运行 1 之后你有 A、B、C，在运行 2 之后你有 A、D、E，你只留下 A。请记住，第二次运行的元素计数两次，所以实际上你有 3"A，这比总数 9 的 1/4。记录每个剩余元素的数量，以跟踪哪些元素可以被丢弃。(您可以始终保留最后的剩余元素，我没有检查过)。

最后你将只有剩下的。根据原始数组检查每一个。