多数元素

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

输入：nums = [3,2,3]
输出：3

输入：nums = [2,2,1,1,1,2,2]
输出：2

方法一：随机化

思路：由于一个给定的下标对应的数字很有可能是众数，我们随机挑选一个下标，检查它是否是众数，如果是就返回，否则继续随机挑选。

# 随机法（超时看运气）
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        target = len(nums) // 2
        while True:
            ans = random.choice(nums)
            if sum(1 for i in nums if i == target) > target:
                return ans

方法二：字典

思路：我们建立一个空字典，对数组 nums 进行迭代，如果键存在，对应的值 +1 。

# 字典
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dict_element = {}
        n = len(nums)
        for i in range(n):
            if nums[i] in dict_element:
                dict_element[nums[i]] += 1
                if dict_element[nums[i]] > (n / 2):
                    return nums[i]
            else:
                dict_element[nums[i]] = 1
                if dict_element[nums[i]] > (n / 2):
                    return nums[i]

方法三：哈希表

思路：我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后，我们遍历哈希映射中的所有键值对，返回值最大的键。我们同样也可以在遍历数组 nums 时候使用打擂台的方法，维护最大的值，这样省去了最后对哈希映射的遍历。

# 哈希表
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = collections.Counter(nums)
        return max(counts.keys(), key = counts.get)

方法四：排序

思路：如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 (n/2) 的元素（下标从 0 开始）一定是众数。

# 排序
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums) // 2]

方法五：分治

思路：我们使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。长度为 1 的子数组中唯一的数显然是众数，直接返回即可。如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。

# 分治
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        def majority_element_rec(lo, hi):
            if lo == hi:
                return nums[lo]
            mid = (hi - lo) // 2 + lo
            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)
            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)

方法六：Boyer-Moore 投票算法

思路：如果我们把众数记为 +1，把其他数记为 ?1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

# Boyer-Moore 投票算法
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        ans = None
        for i in nums:
            if count == 0:
                ans = i
            if i == ans:
                count += 1
            else:
                count -= 1
        return ans