169.多数元素.py

#
# @lc app=leetcode.cn id=169 lang=python3
#
# [169] 多数元素
#
# https://leetcode.cn/problems/majority-element/description/
#
# algorithms
# Easy (66.40%)
# Likes:    2062
# Dislikes: 0
# Total Accepted:    817.8K
# Total Submissions: 1.2M
# Testcase Example:  '[3,2,3]'
#
# 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
#
# 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
#
#
#
# 示例 1：
#
#
# 输入：nums = [3,2,3]
# 输出：3
#
# 示例 2：
#
#
# 输入：nums = [2,2,1,1,1,2,2]
# 输出：2
#
#
#
# 提示：
#
#
# n == nums.length
# 1 <= n <= 5 * 10^4
# -10^9 <= nums[i] <= 10^9
#
#
#
#
# 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
#
#

# @lc code=start
from typing import List


class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        """使用 dict, 空间复杂度最差情况为 O(n)"""
        d = dict()
        max_count = 0
        item = None
        for i in nums:
            count = d.get(i, 0) + 1
            if count > max_count:
                max_count = count
                item = i
            d[i] = count
        return item


# @lc code=end