什么是摩尔投票算法

摩尔投票算法是一种用于在数组中找到出现次数超过一半的元素的算法。该算法的基本思想是通过不断消除不同的元素对，最终找到出现次数超过一半的元素。

算法的具体步骤如下：

1. 初始化候选元素为数组的第一个元素，计数器为1。
2. 遍历数组，对于每个元素：
   • 如果计数器为0，则将当前元素设为候选元素，并将计数器设为1。
   • 如果当前元素与候选元素相同，则计数器加1。
   • 如果当前元素与候选元素不同，则计数器减1。
3. 最终剩下的候选元素即为出现次数超过一半的元素。

该算法的时间复杂度为O(n)，空间复杂度为O(1)。由于出现次数超过一半的元素只可能有一个，因此该算法能够快速找到该元素。