Leetcode 229. Majority Element II
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:
Output:
Example 2:
Input:
Output:
class Solution:
def majorityElement(self, nums: List) -> List:
num1, num2, c1, c2 = 0, 0, 0, 0
for num in nums:
if num == num1:
c1 += 1
elif num == num2:
c2 += 1
elif c1 == 0:
num1 = num
c1 = 1
elif c2 == 0:
num2 = num
c2 = 1
else:
c1 -= 1
c2 -= 1
c1 = c2 = 0
for num in nums:
if num == num1:
c1 += 1
elif num == num2:
c2 += 1
result = []
length = len(nums) // 3
if c1 > length:
result.append(num1)
if c2 > length:
result.append(num2)
return result
页:
[1]