6.10.2022 Lintcode每日打卡 46 主元素

137 阅读 0 评论 91 点赞

我是靠谱客的博主标致玫瑰，这篇文章主要介绍6.10.2022 Lintcode每日打卡 46 主元素，现在分享给大家，希望可以做个参考。

描述

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

背完这套刷题模板，真的不一样！

北大计院令狐冲15年刷题经验总结《算法小抄模板Cheat Sheet》助你上岸！

微信添加【jiuzhang0607】备注【Cheat Sheet】领取

假设数组非空，且数组中总是存在主元素。

样例

样例 1：

输入：

复制代码

1
数组 = [1, 1, 1, 1, 2, 2, 2]

输出：

复制代码

1
1

解释：

数组中1的个数大于数组元素的二分之一。

样例 2：

输入：

复制代码

1
数组 = [1, 1, 1, 2, 2, 2, 2]

输出：

复制代码

1
2

解释：

数组中2的个数大于数组元素的二分之一。

挑战

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

代码：

把元素都放进字典里面，然后再算最大就好了

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from typing import (
    List,
)

class Solution:
    """
    @param nums: a list of integers
    @return: find a  majority number
    """
    def majority_number(self, nums: List[int]) -> int:
        numDict={}
        for i in nums:
            if i in numDict:
                numDict[i]+=1
            else:
                numDict[i]=1
        return max(numDict,key=numDict.get)