字符串出现次数的TopK问题

字符串出现次数的TopK问题_牛客题霸_牛客网

问题简述

给定一个字符串数组，再给定整数 k ，请返回出现次数前k名的字符串和对应的次数。
返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。

思路1：自定义排序

• 时间复杂度：O(NlogN)；

Python

class Solution:
    def topKstrings(self , strings: List[str], k: int) -> List[List[str]]:
        from collections import Counter
        ret = sorted(Counter(strings).items(), key=lambda x: (-x[1], x[0]))
        return ret[:k]

思路2：堆

• 时间复杂度：O(NlogK)；

Python

class Solution:
    def topKstrings(self , strings: List[str], k: int) -> List[List[str]]:
        from collections import Counter
        import heapq
        
        # 定义一个结构，使支持自定义排序
        class Item:
            def __init__(self, s, c):
                self.s = s
                self.c = c
            
            def __lt__(self, o):
                if self.c == o.c:
                    return self.s > o.s  # 字符顺序
                return self.c < o.c  # 频率逆序
        
        # 初始化小顶堆，即保存最大的 k 个元素，且堆顶是最小的
        h = []
        cnt = list(Counter(strings).items())
        for i in range(k):
            s, c = cnt[i][0], cnt[i][1]
            heapq.heappush(h, Item(s, c))
        
        # 遍历剩余元素
        for i in range(k, len(cnt)):
            s, c = cnt[i][0], cnt[i][1]
            it = Item(s, c)
            if it > h[0]:  # 如果大于堆顶，更新 TopK
                heapq.heappop(h)
                heapq.heappush(h, it)
        
        ret = []
        while h:
            it = heapq.heappop(h)
            ret.append([it.s, it.c])
        
        # 因为是小顶堆，所以要逆序输出
        return ret[::-1]