Leetcode 229. Majority Element II

Seawolf

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. class Solution:
   
2.     def majorityElement(self, nums: List[int]) -> List[int]:
   
3.         num1, num2, c1, c2 = 0, 0, 0, 0
   
4.         
   
5.         for num in nums:
   
6.             if num == num1:
   
7.                 c1 += 1
   
8.             elif num == num2:
   
9.                 c2 += 1
   
10.             elif c1 == 0:
    
11.                 num1 = num
    
12.                 c1 = 1
    
13.             elif c2 == 0:
    
14.                 num2 = num
    
15.                 c2 = 1
    
16.             else:
    
17.                 c1 -= 1
    
18.                 c2 -= 1
    
19.         
    
20.         
    
21.         c1 = c2 = 0
    
22.         
    
23.         for num in nums:
    
24.             if num == num1:
    
25.                 c1 += 1
    
26.             elif num == num2:
    
27.                 c2 += 1
    
28.         
    
29.         result = []
    
30.         length = len(nums) // 3
    
31.         
    
32.         if c1 > length:
    
33.             result.append(num1)
    
34.         if c2 > length:
    
35.             result.append(num2)
    
36.         return result

复制代码