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

Question

所以我在网上发现了这个Google采访算法问题.这真的很有趣,我还没有找到一个好的解决方案.请看一下,并给我一个提示/解决方案,如果你能用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和Moore的线性时间投票算法

更好的提示:首先考虑解决大多数问题.也就是说,尝试找到至少出现的元素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为当前元素并将count设置为1.

接下来,您需要检查此元素是否确实至少发生过n/2一次,但这可以在一次传递中完成.