优质文章,第一时间送达! Leetcode最新上线了手机版app,之前手机只能通过浏览器登录网站学习,如今有app,闲了就可以瞅两道题。今天等车的时候随手翻了一道题 169. 多数元素 http://leetcode-cn.com/problems/majority-element/。 看了下是众数问题,脑子简单过了下大概思路,就准备接着看其他题了。但想想还是看下别人是怎么做的吧,结果…. 关于题目
暴力解法 先来看看最简单无脑的暴力解法,详细大多数人都能想到该解题方式:
先计算列表1/2的长度,然后进行for循环嵌套最终获取结果。这种时间复杂度:O(n*n)的解法就不多赘述了。主要看看下面两种解法。 哈希表 这种方法,在LeetCode上很常见,就是使用Counter的方式,生成针对元素与出现次数的字典,然后进行计算。
本来觉得没什么特别,但当看到return操作时,觉得自己几年的Python都白学了。居然不知道max函数,具有key的方法…一直是用它来简单的比较最大值。殊不知针对字典操作时,max可以通过定义key值来进行动态比较。(类似的方法如sorted倒是经常使用)… 不知道max有key这个参数的,举个手,让我知道我不是一个人,哈哈… 奇思妙想 最让我佩服的就是下面这种解题思路,堪称经典。 文中定义有一个关键点,多数元素是指数据中出现大于n/2的元素。那么如果所有数字被单调递增或者单调递减的顺序排了序,当n是奇数时,众数的下标为n/2,当n是偶数时,下标为n/2 +1。于是出现了下面这种犀利的解法。
然而,官方的答案还远不止这些,一共提供了六种解答方式。所以,你觉得自己Python学到位了吗? |