Leetcode【347、378、451、692】

问题描述：【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)]