找数组中的多数元素，分治法有点看不懂，附代码
大佬们， 萌新最近在刷题， 看到一个答案用了分治法 有点看不懂，求大佬们帮忙解释一下啊：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入:
输出: 3
示例 2:
输入:
输出: 2
class Solution:
def majorityElement(self, nums, lo=0, hi=None):
def majority_element_rec(lo, hi):
# base case; the only element in an array of size 1 is the majority
# element.
if lo == hi:
return nums
# recurse on left and right halves of this slice.
mid = (hi-lo)//2 + lo
left = 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 == left)
right_count = sum(1 for i in range(lo, hi+1) if nums == right)
return left if left_count > right_count else right
return majority_element_rec(0, len(nums)-1)
问题：上边定义的lo和hi分别指的什么啊？ mid 又是什么啊？？ mid = (hi-lo)//2 + lo 这个关系式是为了得到什么啊？？？ 呜呜呜呜 求大佬敲打我 我只记得我是这么做的，你可以参考一下？class Solution:
def majorityElement(self, nums: List) -> int:
nums=nums.__iter__()
res=nums.__next__()
count=1
for i in nums:
if i==res:
count+=1
elif count==1:
res=i
else:
count-=1
return res 代码有点错，原代码的结果只能返回列表最后一个元素，修改了一下，你要知道的内容，代码里有注释：
class Solution:
def majorityElement(self, nums, lo=0, hi=None): #lo是列表低位索引值，初始化就是0了，hi是列表高位索引值，要由len算出来，这里先赋值None，赋值为0也行
def majority_element_rec(lo, hi):
# 只剩一个元素时，返回元素
if lo == hi:
return nums
# 数组切片位两等份进行递归运算
mid = (hi-lo)//2 + lo #mid是算出的列表中间位索引值
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 == left) #原代码有错，num改成num
right_count = sum(1 for i in range(lo, hi+1) if nums == right) #原代码有错，num改成num
return left if left_count > right_count else right
return majority_element_rec(0, len(nums)-1)
txxcat 发表于 2020-4-20 20:53
代码有点错，原代码的结果只能返回列表最后一个元素，修改了一下，你要知道的内容，代码里有注释：
哇， 谢谢大佬， 能看明白了。 但是自己估计是想不到这么做。。。{:5_104:} 谢谢大佬
页:
[1]