https://leetcode-cn.com/problems/majority-element-ii/
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
示例 1:
输入: [3,2,3]
输出: [3]
示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]
解法一（未验证）：
因为 众数次数是 超过⌊ n/3 ⌋ ，所以不能直接用摩尔投票。
既然是n/3，那么只能有一个或两个数字是众数。这样的话，我们把数组两两一组，如果数组长度是奇数，最后一个数一组。这样总的组数是 ⌊ n/2⌋ , ⌊ n/2⌋ < 2*⌊ n/3 ⌋ 满足使用摩尔投票的条件。
根据摩尔投票的思想，先假设第一组的两个数是众数,a1,a2，初始计数值cnt1,cnt2都为1，然后遍历后面每一组。如果该组中有a1,则cnt1加1，否则减一；如果该组中有a2,则cnt2加1，否则减一。如果cnt1或cnt2减为0，就用该组的值替换（比如此时cnt1为0，该组值为[a2,x],就用x 替换a1。如果cnt1,cnt2同时为0，就用该组的两个值替换a1,a2）。遍历到最后即可。
这个解法我还没有验证，有兴趣的朋友可以验证一下。
网友评论