Q:

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

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

示例 1:

输入: [3,2,3]

输出: [3]

示例 2:

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

输出: [1,2]

A:

一个叫摩尔投票的算法，可以在一次遍历中找出一个数组中的众数（出现次数一半以上的）。通过设置一个计数器和当前‘众数’，若再遇到当前众数计数器加1，遇到其他数字减一，计数器归零时更新当前众数。巧妙之处是每次归零时前面划去的元素都是一半为之前的众数，一半为其他，故剩下的元素序列的众数依然为原来整个序列的众数。

#

# @lc app=leetcode.cn id=229 lang=python3

#

# [229] 求众数 II

#

from collections import defaultdict

class Solution:

    def majorityElement(self, nums: List[int]) -> List[int]:

        candidate1,candidate2=None,None

        cnt1,cnt2=0,0

        l=len(nums)

        for num in nums:

            if num==candidate1:

                cnt1+=1

            elif num==candidate2:

                cnt2+=1

            elif cnt1==0:

                candidate1=num

                cnt1=1

            elif cnt2==0:

                candidate2=num

                cnt2=1

            else:

                cnt1-=1

                cnt2-=1

        return [x for x in [candidate1,candidate2] if nums.count(x)>l//3]

巴特西

229. 求众数 II

Q:

A:

最新文章

热门文章