0229._majority_element_ii.md

229. Majority Element II

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/majority-element-ii/description/

内容描述

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]
Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

参考oterman

摩尔投票升级版，超过n/3的数最多只能有两个；

• 先选出两个候选人A,B,遍历数组，如果投A（等于A），则A的票数加1;如果投B，B的票数加1；
• 如果A,B都不投（即与A，B都不相等）,那么检查此时是否AB中候选人的票数是否为0，如果为0,则成为新的候选人；
• 如果A,B两个人的票数都不为0，那么A,B两个候选人的票数均减1；
• 遍历结束后选出两个候选人，但是这两个候选人是否满足>n/3，还需要再遍历一遍数组，找出两个候选人的具体票数

beats 96.93%

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums or len(nums) == 0:
            return []
        count1, count2, candidate1, candidate2 = 0, 0, nums[0], nums[0]
        for num in nums:
            if num == candidate1: # 投A
                count1 += 1
                continue
            if num == candidate2: # 投B
                count2 += 1
                continue
            # 此时A,B都不投,检查是否有票数为0情况，如果为0，则更新候选人
            if count1 == 0:
                candidate1 = num
                count1 += 1
                continue
            if count2 == 0:
                candidate2 = num
                count2 += 1
                continue
            # 此时两个候选人的票数都大于1，且当前A和B都不投，那么A,B对应的票数都要--;
            count1 -= 1
            count2 -= 1
        # 上一轮遍历找出了两个候选人，但是这两个候选人是否均满足票数大于N/3仍然没法确定，需要重新遍历，确定票数
        count1, count2 = 0, 0
        for num in nums:
            if num == candidate1:
                count1 += 1
            elif num == candidate2:
                count2 += 1
        res = []
        if count1 > len(nums) / 3:
            res.append(candidate1)
        if count2 > len(nums) / 3:
            res.append(candidate2)
        return res