2

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

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

4

2 回答 2

5

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

主要技巧如下。如果您查看任何四个元素并且它们都是不同的，您可以将所有四个元素都扔掉。（如果任何抛出的元素在旧数组中的频率超过 1/4，它将在新数组中；如果没有，则不会）。

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

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

最后，您将只剩下剩菜。对照原始数组检查每一项。

于 2013-11-05T08:38:10.003 回答
-2

这个元素有三种可能性，要么是数组的中位数，要么是数组的 n/2 个最小元素的中位数，要么是数组的 n/2 个最大元素的中位数。

在所有情况下，首先找到数组的中位数。之后检查它是否至少出现在 n/4 个元素中，如果没有，则将数组分成大小几乎相同的两部分（它们的大小最多相差一个元素）：

  • 小于等于中位数
  • 大于等于中位数

然后找到这两个子数组中的每一个的中值并检查它们中每个子数组的出现次数。这在所有 O(n) 中。同样通过这种方式，您可以找到至少出现 n/4 次的所有元素。

顺便说一句，您可以扩展此技术以查找任何出现时间为 O(n) 的元素（例如 n/10000），这在 O(n) 中再次起作用。

于 2013-11-05T09:41:21.553 回答