Leetcode练习，Python：数组类：第229题：给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 说明: 要求算法的时间复杂度为 O
题目：
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。 说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
思路：
思路1：使用函数；思路2：使用投票法
程序1：使用函数
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
length = len(nums)
if length <= 0:
return []
if length == 1:
return [nums[0]]
result = []
key = length / 3
for num in set(nums):
if nums.count(num) > key:
result.append(num)
return result
程序2：投票法
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
length = len(nums)
if length <= 0:
return []
if length == 1:
return [nums[0]]
result = []
key = length // 3
counter1 = 0
counter2 = 0
candidate1 = 0
candidate2 = 0
for num in nums:
if candidate1 == num:
counter1 += 1
elif candidate2 == num:
counter2 += 1
elif counter1 == 0:
candidate1 = num
counter1 = 1
elif counter2 == 0:
candidate2 = num
counter2 = 1
else:
counter1 -= 1
counter2 -= 1
counter1 = 0
counter2 = 0
for num_1 in nums:
if candidate1 == num_1:
counter1 += 1
if candidate2 == num_1:
counter2 += 1
if counter1 > key and candidate1 != candidate2:
result.append(candidate1)
if counter2 > key and candidate1 != candidate2:
result.append(candidate2)
if counter1 > key and candidate1 == candidate2:
result.append(candidate1)
return result