题目描述

给定一个数组，找这个数组中的主元素，主元素是元素出现次数大于⌊ n/2 ⌋的元素。假设给定的数组非空，主元素都存在，假定只有一个正确答案。

我的解法1——暴力遍历+hash

用hash存已经遍历过（即已排除的）的数，稍微降低算法复杂度
两层循环，n²的复杂度。
结果：beat 49.69%

class Solution(object):
    def majorityElement(self, nums):

        length = len(nums)/2
        dic = {}
        for i in nums:
            now = 0
            if(i in dic):
                continue
            else:
                dic[i] = 1
            for j in nums:
                if(i == j):
                    now += 1
                    if(now > length):
                        return i

我的解法2——排序取中位数

排序后取中位数即可
复杂度nlogn
结果：beat 94.35%

class Solution(object):
    def majorityElement(self, nums):

        nums.sort()
        return nums[len(nums)/2]
        

简便解法1——hash数数后遍历

利用hashtabel，最后遍历一下hashtable即可。
一层循环，n的复杂度

class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

简便解法2——分治

在数组的左右两半上递归，直到区间长度为1。如果当前区间长度大于1，则必须将区间的左右两半的答案组合起来。
- 如果要合并的两个区间的多数元素一致，那么整个切片的多数元素显然是相同的。
- 否则，只有其中一个可以是“正确的”，所以我们需要计算左右多数元素的出现，以确定哪个子片的答案是全局正确的。
时间复杂度T(n) = 2T(n/2) + 2n = nlogn

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)
            

简便方法3——摩尔投票算法

好方法！！！
本质上也是一种分治法
每次从数组中找出一对不同的元素，将它们从数组中删除，直到遍历完整个数组。由于这道题已经说明一定存在一个出现次数超过一半的元素，所以遍历完数组后数组中一定会存在至少一个元素。上面就是这种算法的思想，删除操作可以在常数时间内完成，但是查找不同的元素无法在常数时间内完成，需要用到以下的Trick。
Trick：在算法执行过程中，使用常量空间来记录一个候选元素c以及它的出现次数f(c)，c即为当前阶段出现次数超过一半的元素。在遍历开始之前，该元素c为空，f(c)=0。然后开始遍历数组A时：
- 如果f(c)为0，表示当前并没有候选元素，也就是说之前的遍历过程中没有找到超过一半的元素。那么，如果超过一半的元素c存在，那么c在剩下的子数组中，出现的次数也一定超过一半。因次我们可以将原始问题转化成它的子问题。此时c赋值为当前元素，同时f(c)=1。
- 如果当前A[i]==c，那么f(c)+=1。（没有找到相同的元素，只需要把相同的元素累加起来）
- 如果当前元素A[i]!=c，那么f(c)-=1（相当于删除一个c），不对A[i]做任何处理（相当于删除A[i]）
如果遍历结束之后，f(c)不为0，那么再次遍历一遍数组，如果c真正出现的频率。
时间复杂度是O(n)，空间复杂度为O(1)。

class Solution:
    def majorityElement(self, nums):
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)
            
        return candidate

参考答案

https://leetcode.com/problems/majority-element/solution/