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

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

进阶:尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

示例

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

解析

1)这道题的解法很多,但第一次见不一定能做出来,所以算法题无他,见多识广而已;

2)本文中主要介绍三种解法,排序法、投票法、统计法,都比较巧妙。

代码示例

1、投票法

因为多数元素是出现次数大于 [n/2] 的元素,所以数组排序后,[n//2] 号元素一定是答案。

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

执行用时:28 ms, 在所有 Python3 提交中击败了 99.74% 的用户.

2、投票法

遍历数组,依次和待选元素比较,如果相同则次数加1,不同则减1,多数元素存在绝对数量优势,遍历完后剩下的就是答案。这也是半数以上算通过的选举方法。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        num = None
        count = 0
        for i in nums:
            if count == 0:
                num = i
            count += 1 if i==num else -1
        return num

执行用时:40 ms, 在所有 Python3 提交中击败了 84.67% 的用户.

3、统计法

前面两种解法,都可以在时间 O(n) 和空间 O(1) 的复杂度上求解,但有一个重要的前提,就是元素个数要超过 [n/2],这是一个很强的条件。

实际场景中,更多的可能是找到出现次数最多的即可,不一定数量上会超过 [n/2],所以统计每个值出现的次数,取最大泛化能力更好。

from collections import Counter

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

执行用时:32 ms, 在所有 Python3 提交中击败了 98.42% 的用户.

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/399