LintCode 47. 主元素 II Python算法

描述

给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的三分之一。

说明

数组中只有唯一的主元素

样例

- 例1:

输入: [99,2,99,2,99,3,3], 
输出: 99.

- 例2:

输入: [1, 2, 1, 2, 1, 3, 3], 
输出: 1.

挑战

要求时间复杂度为O(n)，空间复杂度为O(1)。

解析

class Solution:
    """
    @param: nums: a list of integers
    @return: The majority number that occurs more than 1/3
    """
    def majorityNumber(self, nums):
        table = {}
        for i, num in enumerate(nums):
            if num not in table:
                table[num] = 1
            else:
                table[num] += 1
        
        for key, value in table.items():
            if value > len(nums) // 3:
                return key

运行结果

最后

以上就是欣喜画板为你收集整理的LintCode 47. 主元素 II Python算法的全部内容，希望文章能够帮你解决LintCode 47. 主元素 II Python算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。