JAVA 牛牛

229. 求众数 II

  • May 02, 2020
  • 0 views
  • 难度：中等
  • 本题涉及算法： 摩尔投票法
  • 思路： 摩尔投票法
  • 类似题型:

题目 229. 求众数 II

给定一个大小为 n 的数组，找出其中所有出现超过 n/3 次的元素。

说明: 要求算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

示例 1:

输入: [3,2,3]
输出: [3]

示例 2:

输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

摩尔投票法的基本思想

在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素，那么这个元素则可能为目标元素。

在算法执行过程中，我们使用常量空间实时记录一个候选元素c以及其出现次数 $f(c)$，c即为当前阶段出现次数超过半数的元素。根据这样的定义，我们也可以将摩尔投票法看作是一种动态规划算法。

程序开始之前，元素c为空，$f(c)=0$。遍历数组A：

  • 如果f(c)为0，表示截至到当前子数组，并没有候选元素。也就是说之前的遍历过程中并没有找到超过 n/3 的元素。那么，如果超过n/3 的元素c存在，那么c在剩下的子数组中，出现次数也一定超过n/3。因此我们可以将原始问题转化为它的子问题。此时c赋值为当前元素, 同时f(c)=1。
  • 如果当前元素 A[i] == c, 那么 $f(c) += 1$。(没有找到不同元素，只需要把相同元素累计起来)
  • 如果当前元素 A[i] == c, 那么 $f(c) += 1$。(没有找到不同元素，只需要把相同元素累计起来)
  • 如果当前元素 A[i] != c，那么 $f(c) -= 1$ (相当于删除1个c)，不对A[i]做任何处理(相当于删除A[i])

解题思路

  1. 根据题型，需要返回出现次数超过 n/3 次的元素，可知最多有两个这样的元素
  2. 我们假设有两个这种元素，根据 摩尔投票法 设这两个元素为候选人

python

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        res = [] # 返回数组
        majorityO = -1 # 候选人1
        majorityT = -1 # 候选人2
        countO = 0 # 候选人1 票数
        countT = 0 # 候选人2 票数
        for num in nums:
            if countO == 0 and num != majorityT:
                majorityO = num
                countO += 1
                continue
            elif countT == 0 and num != majorityO:
                majorityT = num
                countT += 1
                continue
            else:
                if majorityO == num:
                    countO += 1
                elif majorityT == num:
                    countT += 1
                else:
                    countO -= 1
                    countT -= 1
        counterO = 0
        counterT = 0

        if countO > 0:
            for num in nums:
                if num == majorityO:
                    counterO += 1
        if counterO > len(nums)//3:
            res.append(majorityO)
        if countT > 0:
            for num in nums:
                if num == majorityT:
                    counterT += 1
        if counterT > len(nums)//3:
            res.append(majorityT)

        return res
Search