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

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

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

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[lo]

            # 数组切片位两等份进行递归运算
            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[i] == left)      #原代码有错，num改成num[i]
            right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right)    #原代码有错，num改成num[i]

            return left if left_count > right_count else right

        return majority_element_rec(0, len(nums)-1)

跳转到最佳答案楼层

永恒的蓝色梦想

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

class Solution:
    def majorityElement(self, nums: List[int]) -> 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

txxcat

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

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[lo]

            # 数组切片位两等份进行递归运算
            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[i] == left)      #原代码有错，num改成num[i]
            right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right)    #原代码有错，num改成num[i]

            return left if left_count > right_count else right

        return majority_element_rec(0, len(nums)-1)

hwang.me

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

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