LeetCode 多数元素题解

LeetCode 多数元素题解题目描述给定一个大小为 n 的数组找到其中的多数元素。多数元素是指出现次数超过 ⌊ n/2 ⌋ 的元素。示例输入nums [3,2,3]输出3解题思路方法分治思路使用分治思想解决多数元素问题。将数组分成左右两部分递归找出左右两部分的多数元素。如果左右两部分的多数元素相同返回该元素。否则统计该元素在整个数组中的出现次数返回出现次数较多的元素。复杂度分析时间复杂度O(n log n)。空间复杂度O(log n)。代码实现方法分治# 多数元素分治 def majority_element(nums): def helper(left, right): if left right: return nums[left] mid (left right) // 2 left_major helper(left, mid) right_major helper(mid 1, right) if left_major right_major: return left_major left_count sum(1 for i in range(left, right 1) if nums[i] left_major) right_count sum(1 for i in range(left, right 1) if nums[i] right_major) return left_major if left_count right_count else right_major return helper(0, len(nums) - 1) # 测试 def test_majority_element(): nums [3, 2, 3] print(majority_element(nums)) # 输出3 if __name__ __main__: test_majority_element()总结多数元素是分治思想的典型应用通过递归分解问题分别计算后合并结果。