每日一道算法之--求众数II

数组摩尔投票法

Word count: 590Reading time: 2 min

 2020/05/14   Share

求众数II

力扣第229题: 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]

1. 排序 + 统计

这道题的问题找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。换个说法,就是求长度超过 ⌊ n/3 ⌋的含有相同元素的子数组.

先对数组排序,这样相同元素就排并在一起
用一个变量left保存当前子数组的起始位置,cur保存子数组元素的值,right确定子数组的终点
通过循环,right一直自增,直到找到不和cur相等的元素,这时判断right - left的长度是否大于⌊ n/3 ⌋
更新cur和left
结束循环

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        if not nums:    return []
        if len(nums) == 1:
            return nums
        nums.sort()
        res = []
        n = len(nums)
        need_len = n // 3
        left, cur = 0, nums[0]
        while left < n:
            right = left
            # 注意判断越界
            while right < n and nums[right] == cur:
                right += 1
            if right - left > need_len:
                res.append(cur)
            if right < n:
                cur = nums[right]
            left = right
        return res

复杂度分析

时间复杂度: 虽然嵌套了两个循环,但是第二层循环中均摊时间复杂度实际为 O(1), 所以总的时间复杂度为 O(n).
空间复杂度: 只用到了两个变量,所以空间复杂度为 O(1).

2. 摩尔投票法

可以参考力扣最热门的题解
作者：wotxdx
链接：https://leetcode-cn.com/problems/majority-element-ii/solution/liang-fu-dong-hua-yan-shi-mo-er-tou-piao-fa-zui-zh/

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        res = []
        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

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/05/14/algorithm-229/

发表日期：May 14th 2020, 9:36:03 pm

更新日期：May 14th 2020, 9:38:31 pm

Next Post

每日一道算法之--前缀和总结
Previous Post

每日一道算法之--Pow(x, n)

CATALOG

1. 求众数II
1. 1.1. 1. 排序 + 统计
  1. 1.1.1. 复杂度分析
2. 1.2. 2. 摩尔投票法

