[已解决]找数组中的多数元素，分治法有点看不懂，附代码

hwang.me

大佬们， 萌新最近在刷题， 看到一个答案用了分治法 有点看不懂，求大佬们帮忙解释一下啊：
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

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

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,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[lo]

            # 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[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)


问题：上边定义的lo和hi分别指的什么啊？ mid 又是什么啊？？ mid = (hi-lo)//2 + lo 这个关系式是为了得到什么啊？？？ 呜呜呜呜 求大佬敲打我

最佳答案

月排行榜 / 总排行榜

txxcat

2020-4-21 04:53:49

代码有点错，原代码的结果只能返回列表最后一个元素，修改了一下，你要知道的内容，代码里有注释：

1. class Solution:
   
2.     def majorityElement(self, nums, lo=0, hi=None): #lo是列表低位索引值，初始化就是0了，hi是列表高位索引值，要由len算出来，这里先赋值None，赋值为0也行
   
3.         def majority_element_rec(lo, hi):
   
4.             # 只剩一个元素时，返回元素
   
5.             if lo == hi:
   
6.                 return nums[lo]
   
7. 
   
8.             # 数组切片位两等份进行递归运算
   
9.             mid = (hi-lo)//2 + lo       #mid是算出的列表中间位索引值
   
10.             left = majority_element_rec(lo, mid)     #对列表左半部分再运算
    
11.             right = majority_element_rec(mid+1, hi)    #对列表右半部分再运算
    
12. 
    
13.             # 如果两部分元素相同，返回元素.
    
14.             if left == right:
    
15.                 return left
    
16. 
    
17.             # 不相同，对比两部分元素并且返回“胜者”
    
18.             left_count = sum(1 for i in range(lo, hi+1) if nums[i] == left)      #原代码有错，num改成num[i]
    
19.             right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right)    #原代码有错，num改成num[i]
    
20. 
    
21.             return left if left_count > right_count else right
    
22. 
    
23.         return majority_element_rec(0, len(nums)-1)

复制代码

跳转到最佳答案楼层

永恒的蓝色梦想

我只记得我是这么做的，你可以参考一下？

1. class Solution:
   
2.     def majorityElement(self, nums: List[int]) -> int:
   
3.         nums=nums.__iter__()
   
4.         res=nums.__next__()
   
5.         count=1
   
6.         
   
7.         for i in nums:
   
8.             if i==res:
   
9.                 count+=1
   
10.             elif count==1:
    
11.                 res=i
    
12.             else:
    
13.                 count-=1
    
14. 
    
15.         return res

复制代码

txxcat

代码有点错，原代码的结果只能返回列表最后一个元素，修改了一下，你要知道的内容，代码里有注释：

1. class Solution:
   
2.     def majorityElement(self, nums, lo=0, hi=None): #lo是列表低位索引值，初始化就是0了，hi是列表高位索引值，要由len算出来，这里先赋值None，赋值为0也行
   
3.         def majority_element_rec(lo, hi):
   
4.             # 只剩一个元素时，返回元素
   
5.             if lo == hi:
   
6.                 return nums[lo]
   
7. 
   
8.             # 数组切片位两等份进行递归运算
   
9.             mid = (hi-lo)//2 + lo       #mid是算出的列表中间位索引值
   
10.             left = majority_element_rec(lo, mid)     #对列表左半部分再运算
    
11.             right = majority_element_rec(mid+1, hi)    #对列表右半部分再运算
    
12. 
    
13.             # 如果两部分元素相同，返回元素.
    
14.             if left == right:
    
15.                 return left
    
16. 
    
17.             # 不相同，对比两部分元素并且返回“胜者”
    
18.             left_count = sum(1 for i in range(lo, hi+1) if nums[i] == left)      #原代码有错，num改成num[i]
    
19.             right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right)    #原代码有错，num改成num[i]
    
20. 
    
21.             return left if left_count > right_count else right
    
22. 
    
23.         return majority_element_rec(0, len(nums)-1)

复制代码

hwang.me

txxcat 发表于 2020-4-20 20:53
代码有点错，原代码的结果只能返回列表最后一个元素，修改了一下，你要知道的内容，代码里有注释：

哇， 谢谢大佬， 能看明白了。 但是自己估计是想不到这么做。。。 谢谢大佬