LeetCode DSA 系列 #7: 169. 多数元素

Source: Dev.to

问题

这是我对挑战第 7 天的尝试（我错过了昨天的提交）。今天的问题是 169. Majority Element。

给定一个大小为 n 的数组 nums，返回多数元素。

多数元素是出现次数超过 ⌊n / 2⌋ 次的元素。你可以假设数组中一定存在多数元素。

解法

from collections import Counter
from typing import List

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = Counter(nums)
        majority = len(nums) / 2

        for k, v in counts.items():
            if v > majority:
                return k

复杂度

• 时间: O(N) – 我们遍历列表一次以构建计数器，再遍历一次以找到多数元素。
• 空间: O(N) – 计数器可能存储多达 N 个不同的元素。