LintCode 47. 主元素 II Python算法

84 阅读 0 评论 56 点赞

我是靠谱客的博主欣喜画板，这篇文章主要介绍LintCode 47. 主元素 II Python算法，现在分享给大家，希望可以做个参考。

描述

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

说明

数组中只有唯一的主元素

样例

复制代码

1
2
3
4
5
6
7
8
9
10
- 例1:

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

- 例2:

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

挑战

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

解析

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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