我在网上找到的一个有趣的谷歌面试算法，需要线性时间

Question

所以我在网上找到了这个谷歌面试算法的问题。这真的很有趣，我还没有想出一个好的解决方案。请看一下，并给我一个提示/解决方案，如果你能用Java :)写代码就太好了。

“设计一种算法，给定数组中n个元素的列表，找出列表中出现n/3次以上的所有元素。该算法应在线性时间内运行。(n >=0 )希望您使用比较并实现线性时间。没有散列/过多空间/并且不使用标准的线性时间确定性选择算法。”

Answer 1

我的解决方案是受到俄罗斯方块游戏的启发。解决方案亮点(被称为“Tetrise process”)：使用三个键值对进行记账，对元素进行键值，计算元素的计数。在主循环中，我们最多保留3个最新的不同元素。当所有三个键的计数都非零时，我们递减所有键的计数，并消除零计数键(如果有)。最后，可能会有一些残留的元素，也可能没有。这些是俄罗斯方块进程的幸存者。请注意，剩余元素不能超过3个。如果什么都没有剩下，我们返回null。否则，我们循环遍历原始的n个元素，计算这些剩余元素的数量，并返回计数> n/3的元素。

证明提示:为了显示上述算法的正确性，请注意，对于一个元素，必须在俄罗斯方块过程中幸存下来或留在残留物中才能满足要求。为了了解原因，让我们将删除操作的数量表示为m和剩余元素的总数r。然后我们有n=3*m+ r。从这里我们得到m <= n/3，因为r >= 0。如果一个元素没有在Tetrise过程中幸存下来，那么它出现的最大次数是m <= n/3。

时间复杂度为O(n)，空间复杂度为O(1)。

Answer 2

提示:看看Boyer and Moore's Linear Time Voting Algorithm

更好的提示:首先考虑解决多数问题。也就是说，尝试找到一个至少出现n/2次的元素。该算法的基本思想是，如果我们用与e不同的所有其他元素来抵消元素e的每次出现，那么如果e是多数元素，那么它将一直存在到最后。

findCandidate(a[], size)
    //Initialize index and count of majority element
    maj_index = 0;
    count = 1;

    for i = 1 to n–1 {
      if a[maj_index] == a[i]
          count++;
      else
          count--;

      if count == 0 {
          maj_index = i;
          count = 1;
      }
    }
    return a[maj_index]

该算法遍历每个元素，并维护a[maj_index]的计数。如果下一个元素相同，则递增计数，如果下一个元素不相同，则递减计数，如果计数达到0，则将maj_index更改为当前元素，并将计数设置为1。

接下来，您需要检查该元素是否确实出现了至少n/2次，但这可以在一次遍历中完成。