描述

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

思考

按照要求，标准答案是摩尔投票，实现很简单
但是如果你不知道摩尔投票，则实现O(n)时间复杂度O(1)空间复杂度就比较困难了
这里我将其转化成问题：寻找第n/2+1大的数字
注意，之前我是发过第k大数字的题解的，这时候就排上用场了
这种O(n)做法也很帅 就是空间因为栈的原因不是O(1)的

class Solution:
    def majorityElement(self, nums: List[int]) -> int:

        def quick_select(nums , k) :
            pivot = random.choice(nums) 
            less , eq , more = [],[],[]
            for x in nums :
                if x < pivot :
                    less.append(x)
                elif x > pivot:
                    more.append(x)
                else :
                    eq.append(x)
            if len(more)>=k :
                return quick_select(more,k)
            elif len(more) + len(eq) < k :
                return quick_select(less,k-len(eq)-len(more))
            return pivot        
        return quick_select(nums,len(nums)//2+1)