网站制作资讯,wordpress coshtmlcache,百度站点提交工具,360推广登陆入口题目#xff1a;
给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n/2⌋ 的元素。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
解题思路#xff1a;
1. 注意“大于 ⌊n/2⌋”#xff0c;…题目
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n/2⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
解题思路
1. 注意“大于 ⌊n/2⌋”因此在将数据排序之后一定可以在⌊n/2⌋的下标位置找到该数字
2. 哈希映射存储每个元素及其出现的次数
3. 由于列表中有众数随机挑选下标并验证
4. 分治“如果数 a 是数组 nums 的众数如果我们将 nums 分成两部分那么 a 必定是至少一部分的众数”
5. Boyer-Moore 投票维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值count 为 0遍历数组 nums 中的所有元素对于每个元素 x在判断 x 之前如果 count 的值为 0我们先将 x 的值赋予 candidate随后我们判断 x如果 x 与 candidate 相等那么计数器 count 的值增加 1x 与 candidate 不等那么计数器 count 的值减少 1在遍历完成后candidate 即为整个数组的众数 Python 解法
class Solution: # 分治def majorityElement(self, nums: List[int]) - int:def majority_element_rec(lo, hi) - int:# base case; the only element in an array of size 1 is the majority# element.if lo hi:return nums[lo]# recurse on left and right halves of this slice.mid (hi - lo) // 2 loleft majority_element_rec(lo, mid)right majority_element_rec(mid 1, hi)# if the two halves agree on the majority element, return it.if left right:return left# otherwise, count each element and return the winner.left_count sum(1 for i in range(lo, hi 1) if nums[i] left)right_count sum(1 for i in range(lo, hi 1) if nums[i] right)return left if left_count right_count else rightreturn majority_element_rec(0, len(nums) - 1)class Solution: # 投票def majorityElement(self, nums: List[int]) - int:count 0candidate Nonefor num in nums:if count 0:candidate numcount (1 if num candidate else -1)return candidate
