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()总结
多数元素是分治思想的典型应用，通过递归分解问题，分别计算后合并结果。
