# Majority Element II

### 描述​

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

Follow-up: Could you solve the problem in linear time and in O(1) space?

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1] > Output: [1]

Example 3:

Input: nums = [1,2] > Output: [1,2]

Constraints:

• 1 <= nums.length <= 5 * $10^4$
• -$10^9$ <= nums[i] <= $10^9$

### 分析​

• 最多只有一个元素能出现超过 ⌊n/2⌋ 次.
• 最多只有两个元素能出现超过 ⌊n/3⌋ 次.
• 最多只有三个元素能出现超过 ⌊n/4⌋ 次.

Boyer-Moore 投票算法就是依据上面的原理而实现的。

### 代码​

# Majority Element II# Time Complexity: O(nlogn), Space Complexity: O(1)class Solution(object):    def majorityElement(self, nums: List[int])->List[int]:        # 1st pass        count1, count2 = 0, 0        # candidates must be initalized to different values        candidate1, candidate2 = 0, 1        for num in nums:            if candidate1 == num:                count1 += 1            elif candidate2 == num:                count2 += 1            elif count1 == 0:                candidate1 = num                count1 = 1            elif count2 == 0:                candidate2 = num                count2 = 1            else:                count1 -= 1                count2 -= 1        # 2nd pass        result = []        for c in [candidate1, candidate2]:            if nums.count(c) > len(nums)/3:                result.append(c)        return result