LeetCode 169：多数元素解法全解析

LeetCode169给定一个大小为n的数组nums返回其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。示例 1输入nums [3,2,3]输出3示例 2输入nums [2,2,1,1,1,2,2]输出2Python解法1.哈希表class Solution: def majorityElement(self, nums: List[int]) - int: counts collections.Counter(nums) return max(counts.keys(), key counts.get)Counter是 Python 内置计数器工具接收可迭代列表统计每个元素出现的次数返回类字典对象key数组里的数字value该数字出现次数counts.keys()取出所有统计过的数字 →[2,1]keycounts.get规定比较规则counts.get(x) 获取数字 x 对应的出现次数max 函数不再比数字本身大小而是比「每个数字的出现次数」最终返回出现次数最大的那个数字题目要求的多数元素2.排序class Solution: def majorityElement(self, nums: List[int]) - int: nums.sort() return nums[len(nums) // 2]#取中间下标返回3.随机化class Solution: def majorityElement(self, nums: List[int]) - int: majority_count len(nums) // 2 while True: candidate random.choice(nums) if sum(1 for elem in nums if elem candidate) majority_count: return candidatemajority_count len(nums) // 2判定门槛出现次数必须严格大于这个数才是答案candidate random.choice(nums)从数组里随机挑一个候选数字生成器表达式统计次数sum(1 for elem in nums if elem candidate)累加相同元素个数4.分治from typing import List class Solution: def majorityElement(self, nums: List[int]) - int: def majority_element_rec(lo, hi) - int: # 递归终止区间只剩单个元素即为当前区间多数元素 if lo hi: return nums[lo] # 二分拆分左右区间 mid (hi - lo) // 2 lo left_candidate majority_element_rec(lo, mid) right_candidate majority_element_rec(mid 1, hi) # 左右区间候选相同直接返回该数 if left_candidate right_candidate: return left_candidate # 候选不同统计当前区间两个数字出现次数 left_cnt sum(1 for idx in range(lo, hi 1) if nums[idx] left_candidate) right_cnt sum(1 for idx in range(lo, hi 1) if nums[idx] right_candidate) # 返回出现次数更多的候选 return left_candidate if left_cnt right_cnt else right_candidate # 递归入口整个数组下标 0 ~ len(nums)-1 return majority_element_rec(0, len(nums) - 1)5.Boyer-Moore 投票算法from typing import List class Solution: def majorityElement(self, nums: List[int]) - int: count 0 candidate None for num in nums: # 票数清零更换候选人为当前数字 if count 0: candidate num # 当前数字和候选相同1不同则抵消-1 count 1 if num candidate else -1 return candidate