首页 > itarticle > 169. majority element

169. majority element

admin 1月 30, 2021 0

Description

Difficulty: Easy

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

给一数列，找出众数。

Solution

扫描一遍 nums，维护一个字典 xSet：
key ：nums 中元素
value：该元素出现次数
再扫描一遍 xSet，找到出现次数大于 floor(len(nums)) 的元素，返回。

import math
class (object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        xSet = {}
        for i in nums:
            try:
                xSet[i] += 1
            except KeyError:
                xSet[i] = 1
        
        for j in xSet:
            if xSet[j] > math.floor(len(nums) / 2):
                return j