Leetcode【347、378、451、692】
Leetcode【347、378、451、692】
echobingo
发布于 2019-07-01 10:58:41
发布于 2019-07-01 10:58:41
问题描述：【Heap】347. Top K Frequent Elements
解题思路：
给一个整数数组，返回最常出现的 k 个元素。
一般情况下，求前 k 个元素的题目可以使用堆求解。但是如果先进行堆排序（O(n*logn)），再输出前 k 个元素，这样时间复杂度和普通排序方法 sorted() 没有区别。
对于求前 k 个元素，实际上我们只需要维护大小为 k 的堆长度即可。当我们的堆达到 k 个元素后，剩下的元素和堆顶的元素比较，如果其出现次数大于堆顶元素，则替换堆顶元素。因为只维护了 k 大小的堆，这种做法的时间复杂度为 O(n*logk)。但是，如果 k = n，时间复杂度还会退化成 O(n*logn)。
Python3 实现：
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
heap = []
for num, cnt in collections.Counter(nums).items():
if len(heap) < k: # 只维护大小为k的堆
heapq.heappush(heap, (cnt, num))
elif cnt > heap[0][0]: # 达到k后，后面的元素和堆顶元素比较
heapq.heapreplace(heap, (cnt, num))
ans = []
while len(heap) > 0: # 输出堆中前k个元素（从小到大）
ans.append(heapq.heappop(heap)[1])
return ans一种 Pythonic 的写法，即利用 collections.Counter(list).most_common(k) 返回前 k 大元素。
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
return [i[0] for i in collections.Counter(nums).most_common(k)]问题描述：【Sort】378. Kth Smallest Element in a Sorted Matrix
解题思路：
这道题是给一个 n*n 矩阵，每行每列都是升序，求第 k 小元素。
先排序，再输出。时间复杂度 O((n^2) * (log (n^2))。实际上也可以使用 Leetcode 347 中的方法进行堆排序。
Python3 实现：
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
N = len(matrix)
return sorted([matrix[i][j] for i in range(N) for j in range(N)])[k-1]问题描述：【Sort】451. Sort Characters By Frequency
解题思路：
这道题是给一个字符串，按照字母次数降序排列。
做法很直接，统计每个单词出现的次数，然后使用 sorted() 从大到小排序即可。
Python3 实现：
class Solution:
def frequencySort(self, s: str) -> str:
dic = collections.Counter(s)
li = sorted(dic.items(), key=lambda x: x[1], reverse=True) #按照次数从大到小排序
ans = ""
for item in li:
ans += item[0] * item[1]
return ans问题描述：【Heap】692. Top K Frequent Words
解题思路：
这道题是给一个单词数组，返回出现次数最多的前 k 个单词。如果次数相同，返回字典序较小的单词。
这道题和 Leetcode 347 类似，但是不同之处在于次数相同时要输出字典序较小的单词。如果使用 sorted() 或者 Counter(words).most_common(k) 方法，均不能实现次数相同输出较小字典序的单词。但是，使用 heapq.nsmallest(k, list) 可以实现这个功能。
时间复杂度为建堆时产生的 O(n*logn)。
Python3 实现：
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
heap = []
for word, cnt in collections.Counter(words).items():
heapq.heappush(heap, (-cnt, word)) # 负值表示建立小根堆
return [h[1] for h in heapq.nsmallest(k, heap)]本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.06.30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录