LeetCode 169.229.求众数



说一句,LeetCode上因为测试用例不严谨,有错的情况,自己理解即可。




题目169:

happysneaker.com



思路:

① 题目说非空、一定存在众数,这道题忽略题目中的 N/2 就按照众数的真正定义来计算

② 首先统计给定的List中每个元素出现的次数,以k/v的方式存到字典中

③ 然后遍历字典,找到最大的value对应的key

④ 

Python 字典(Dictionary) keys() 函数以列表返回一个字典所有的键。

Python 字典(Dictionary) values() 函数以列表返回字典中的所有值。

Python 字典(Dictionary) items() 函数以列表返回可遍历的(键, 值) 元组数组。

happysneaker.com

⑤ list.count(x) :求list里x的个数

⑥ 循环遍历list生成字典方法: dict( (key,value) for key in list ) 

⑦ 字典根据value 求对应的key :res=[ k for k,v in dict.items() if v==max(dict.values()) ] ,注意res只能用 []接收,不能用() 因为元组不可变而res可能有多个值。


解:

class Solution:
    def majorityElement(self, nums):
        x=dict((a,nums.count(a)) for a in nums)  #将每个元素对应的个数存到字典里
        y=[k for k,v in x.items() if v==max(x.values())]  #找到字典里最大值对应的key,可能有多个所以放到[]
        return y

happysneaker.com







题目229:

happysneaker.com


思路:

① 思路和上面差不多,也是利用字典,同时需要考虑到桶排序的思想

② 个数超过N/3即 >N/3  ,所以得先n=len(nums)统计共多少个数

③ 结合桶排序思想,将num本身作为k,而num的个数作为v ,存放到dict中

④ 以③的方式遍历nums插入dict,最后统计 v >N/3 的 k 即可



解:

class Solution(object):
    def majorityElement(self, nums):
        n=len(nums)
        dict={}
        for num in nums:
            if num in dict:   #如果num已经存在dict中,那么num作为k ,出现次数v 加一
                dict[num]+=1                
            else:           #如果num是第一次出现,那么v 设为一
                dict[num]=1
        return [num for num in dict.keys() if dict[num]>n/3]  #返回结果num,遍历dict的keys,查找条件是num的出现次数>N/3






Web安全技术分享
请先登录后发表评论
  • 最新评论
  • 总共1条评论
Web安全技术分享

./7vs10.com

2019-03-19 13:06:16 回复