分治算法【二】——应用：Leetcode169：多数元素

题目：多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

这里主要是以分治算法来求解这道题，关于分治算法的思路，可以click here, 有关很多的其它解法可看leetcode官方解法。

1、 要解决什么？

这里解决的问题很简单，就是跟你一个数组，找出其中的众数。

2、回想以下分治算法步骤？

分解 ==> 求解 ==> 合并

3、这题如何使用分治算法？

首先就是要将给定的数组分成两部分【分解】，分别求解这两部分的众数【求解】，然后比较这两部分的众数，最终得出结果【合并】。

注意，我们要设定边界条件。

假设，lo、hi分别是选取数组的左边索引，右边索引（包括lo和hi），mid是切分的位置 给定一个数组a[lo, hi]

分解： mid = 索引的中间位置， (hi - lo) // 2 + lo 则左边数组为 left = a[lo, mid] 右边数组为 right = a[mid + 1, hi]

求解： 对于分解的两部分数据进行递归求解

合并： 统计左右两边的众数出现的次数，返回结果

class Solution: def majorityElement(self, nums: List[int]) -> int: def majority_element_rec(lo, hi): # 边界条件，或递归终止条件 if lo == hi: return nums[lo] # 计算lo、hi的中间索引 mid = (hi - lo) // 2 + lo # 分解、求解左边数组的众数和右边数组的众数 left = majority_element_rec(lo, mid) right = majority_element_rec(mid + 1, hi) if left == right: return left # 归并 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 right return majority_element_rec(0, len(nums)-1)