有关递归与分治的做题笔记，Python实现

169. 求众数 Majority Element

LeetCodeCN 第169题链接

第一种方法：两重循环暴力求解

第二种方法：哈希表记录每个元素出现次数，发现出现超过n/2的就是众数

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        leng = len(nums)
        if leng == 1:
            return nums[0]
        dic = {}
        for i in nums:
            if i in dic:
                dic[i] += 1
                if dic[i] >= leng / 2:
                    return i
            else:
                dic[i] = 1

第三种方法：排序后直接返回中间值，因为题目限定条件必然存在众数

def majorityElement(self, nums: List[int]) -> int:
    return sorted(nums)[len(nums)//2]

第四种方法：用list.count()方法

def majorityElement(self, nums: List[int]) -> int:
    # 此处如果遍历整个nums会超时
    for i in nums[len(nums)//2:]:
        if nums.count(i) > len(nums)//2:
            return i

第五种方法：分治

def majorityElement(self, nums):
    if not nums:
        return None
    if len(nums) == 1:
        return nums[0]
    a = self.majorityElement(nums[:len(nums)//2])
    b = self.majorityElement(nums[len(nums)//2:])
    if a == b:
        return a
    return [b, a][nums.count(a) > len(nums)//2]
    
    # 这个 return 的写法等同于下面的 if else
    # 因为若后一个[]里为True即1所以取[b,a][1]=a, False即0取[b,a][0]=b
    # 
    # if nums.count(a) > len(nums)//2:
    #     return a
    # else:
    #     return b