给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

 

 

废话不多说

直接分治

 1 class Solution:
 2     def majorityElement(self, nums: List[int]) -> int:
 3         def help(low,high):
 4             if low == high:
 5                 return nums[low]
 6             mid = (high-low)//2 + low
 7             left = help(low,mid)
 8             right = help(mid+1,high)
 9             if left == right:
10                 left
11             left_count = sum(1 for i in range(low,high+1) if nums[i]==left)
12             right_count = sum(1 for i in range(low,high+1) if nums[i]==right)
13             return left if left_count > right_count else right
14         return help(0,len(nums)-1)

2020-01-13 19:33:54