优质文章,第一时间送达!
Leetcode最新上线了手机版app,之前手机只能通过浏览器登录网站学习,如今有app,闲了就可以瞅两道题。今天等车的时候随手翻了一道题
169. 多数元素 http://leetcode-cn.com/problems/majority-element/。
看了下是众数问题,脑子简单过了下大概思路,就准备接着看其他题了。但想想还是看下别人是怎么做的吧,结果….
关于题目
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
暴力解法
先来看看最简单无脑的暴力解法,详细大多数人都能想到该解题方式:
1class Solution:
2 def majorityElement(self, nums):
3 majority_count = len(nums)//2
4 for num in nums:
5 count = sum(1 for elem in nums if elem == num)
6 if count > majority_count:
7 return num
先计算列表1/2的长度,然后进行for循环嵌套最终获取结果。这种时间复杂度:O(n*n)的解法就不多赘述了。主要看看下面两种解法。
哈希表
这种方法,在LeetCode上很常见,就是使用Counter的方式,生成针对元素与出现次数的字典,然后进行计算。
1class Solution:
2 def majorityElement(self, nums):
3 counts = collections.Counter(nums)
4 return max(counts.keys, key=counts.get)
本来觉得没什么特别,但当看到return操作时,觉得自己几年的Python都白学了。居然不知道max函数,具有key的方法…一直是用它来简单的比较最大值。殊不知针对字典操作时,max可以通过定义key值来进行动态比较。(类似的方法如sorted倒是经常使用)…
不知道max有key这个参数的,举个手,让我知道我不是一个人,哈哈…
奇思妙想
最让我佩服的就是下面这种解题思路,堪称经典。
文中定义有一个关键点,多数元素是指数据中出现大于n/2的元素。那么如果所有数字被单调递增或者单调递减的顺序排了序,当n是奇数时,众数的下标为n/2,当n是偶数时,下标为n/2 +1。于是出现了下面这种犀利的解法。
1class Solution:
2 def majorityElement(self, nums):
3 nums.sort
4 return nums[len(nums)//2]
然而,官方的答案还远不止这些,一共提供了六种解答方式。所以,你觉得自己Python学到位了吗?
推荐阅读:苹果x与xr哪个好
-
同样是茶,在18个国家竟有18种吃法
同样是茶,在18个国家竟然有18种吃法!!同样是茶,这吃法差别咋就这么大呢!!下面小编让大家了解一下18个不同的国家是怎么品茶的。1.日本用天然石磨碾磨成超微粉...
2019-12-18 -
KFC新品评测:薯片做炸鸡、“豆瓣味”的汉堡
圣诞节作为西方最重要的节日之一,一直有着极强的存在意义,虽然在中国它已经失去了本来的宗教象征,沦为了商家们营销狂欢的大节,但不可否认,大家还挺吃这一套的。肯德基...
2019-12-18 -
马未都:虾仁
北京人都管虾叫虾米,不叫虾。全中国最有名的画家齐白石画什么最出名?北京人一定回答说是大虾米。一个孩子驼背,大人一定拍着他的后背说,直起虾米腰来!我有个朋友腰驼得...
2019-12-18 -
蛋糕虽然越来越好吃,但如今也越卖越贵了,这是
相信很多人都有吃过蛋糕这种食物,当然一说到蛋糕很多人就会想到现在年轻人生日的时候吃的生日蛋糕。不过蛋糕在西方不仅可以在生日的时候吃,在日常的生活中也是作为一种饭...
2019-12-18 -
甄嬛传里的美食大赏,每一样都能让人念念不忘
甄嬛传是一部经典的宫斗剧,后宫里的美人儿多,手段高,风景好,但最让人眼馋的还是一道道精致的菜品,每一样都能让人念念不忘。东阿阿胶桂圆羹沈眉庄落水之夜,华妃盛装出...
2019-12-18 -
成功击退康师傅!中国最赚钱的零食诞生,利润是
零食,作为人们生活中必不可少的食品而言,不仅可以解馋,还可以打发时间。而且根据专家研究表明,吃零食在满足肚子饥饿需要的同时,还能缓解人的紧张情绪和内心的冲突。说...
2019-12-18