很经典的排序问题 (๑• . •๑)
先看题目,“前K个高频元素”
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
这题很简单,两步:
那么第一步就不用说了,很简单
m = dict()
for num in nums:
if num in m:
m[num] += 1
else:
m[num] = 1
有趣的就在第二步,排序。很多人都是使用内置库sorted
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
m = dict()
for num in nums:
if num in m:
m[num] += 1
else:
m[num] = 1
output = sorted(m.items(), key=lambda e: e[1], reverse=True)
final = []
for i in range(k):
final.append(output[i][0])
return final
最简洁的代码是直接使用Python内置的collections
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
import collections
counter = collections.Counter(nums)
return [item[0] for item in counter.most_common(k)]
这真是是我们想要的吗?并不是。我们的目标是不使用任何内置库。
关于Python的sorted排序算法,这篇文章讲的比较详细:python sort函数内部实现原理,说到Python使用的是著名的Timesort
算法。
Timsort
是结合了合并排序(merge sort)和插入排序(insertion sort)而得出的排序算法,它在现实中有很好的效率。
Tim Peters在2002年设计了该算法并在Python中使用(TimSort 是 Python 中 list.sort 的默认实现)。该算法找到数据中已经排好序的块-分区,每一个分区叫一个run,然后按规则合并这些run。Pyhton自从2.3版以来一直采用Timsort算法排序,现在Java SE7和Android也采用Timsort算法对数组排序。
如果想自己用Python来写一个排序算法,完成本题要求该如何写?也就是对这个字典进行排序,{5: 1, 1: 3, 4: 1, 2: 2, 3: 1}
,有什么好办法。
思路可以是两个指针遍历字典,如果左边大于右边,则替换位置。
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
m = dict()
for num in nums:
if num in m:
m[num] += 1
else:
m[num] = 1
bucket = [[] for _ in range(len(nums) + 1)]
for key, value in m.items():
bucket[value].append(key)
result = []
for i in range(len(nums), 0, -1):
for n in bucket[i]:
result.append(n)
if len(result) == k:
return result
return result
很巧妙的使用列表的索引来保存value。
此时bucket值是[[], [5, 4, 3], [2], [1], [], [], [], [], []]
,索引即出现次数。
此解法用时72ms,战胜 50.84 % 的 python3 提交记录。但是看了排在前面的算法,都是使用的Python内置的collections
。
如果是你,会用什么方法呢?
本文分享自 Python爬虫与算法进阶 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!