力扣刷题Python笔记:多数元素

题目

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

力扣刷题Python笔记:多数元素
来源:力扣(LeetCode)

Python解法

哈希表解法

这道题我想的是建立一个字典,字典的键为数组元素,对应的值是该元素在数组中出现的次数,然后遍历字典中的值,如果值大于数组长度的一半,则返回对应的键。

代码如下:

def majorityElement(self, nums: List[int]) -> int:
    dict_count = {}
    for i in nums:
        dict_count[i] = dict_count.get(i, 0) + 1
    n = len(nums)
    for key, value in dict_count.items():
        if value > n/2:
            return key

排序解法

看到题解中一种超简单的解法:既然“多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素”,那我们对数组排序之后取中间的数,该数一定是我们要求的多数元素。

代码如下:

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

摩斯投票法

题解中还提出了一种方法——摩尔投票法,也被称作「多数投票法」。算法解决的问题是:如何在任意多的候选人中(选票无序),选出获得票数最多(必须超过得票数一半)的那个。

该算法可以分为两个阶段:①对抗阶段:分属两个候选人的票数进行两两对抗抵消;②计数阶段:计算对抗结果中最后留下的候选人票数是否有效。

根据上述的算法思想,我们遍历投票数组,将当前票数最多的候选人与其获得的(抵消后)票数分别存储在 major 与 count 中。

当我们遍历下一个选票时,判断当前 count 是否为零:

  • 若 count == 0,代表当前 major 空缺,直接将当前候选人赋值给 major,并令 count++;
  • 若 count != 0,代表当前 major 的票数未被完全抵消,因此令 count–,即使用当前候选人的票数抵消 major 的票数

代码如下:

def majorityElement(self, nums: List[int]) -> int:
    major = 0
    count = 0
    for n in nums:
        if count == 0:
            major = n
        if n == major:
            count += 1
        else:
            count -= 1
    return major
上一篇:摩尔投票算法


下一篇:python之字符格式化