题目翻译

给定大小为n的数组，查找多数元素。多数元素是出现次数超过 n/2 次的元素。

注

可以假定数组是非空的，并且多数元素始终存在于数组中。

题目思路1

1. 使用collections模块的Counter()类统计数组中每个元素出现的次数 num 。
2. 依次将每个元素出现的次数 num 与 n/2 比较，若大于 n/2 则返回当前元素，若小于 n/2 则检查下一个元素。

代码如下：

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        import collections
        key_dict = {}
        key_dict = collections.Counter(nums)
        for key, count in key_dict.items():
            if count > len(nums) / 2:
                return key
            else:
                key += 1

程序的时间复杂度为 O(n).

PS

新手刷leetcode, 如有错误和建议请帮忙指出，谢谢。