题解 | #字符串出现次数的TopK问题#

题意整理：
给定一个字符串数组，再给定整数k，请返回出现次数前k名的字符串和对应的次数。
解法一：
思路：
这是一种比较简单的解法，首先利用python中collection包下Counter的类，对字符串出现的次数进行统计。然后利用字典排序的方法，先对字典的值进行排序，再对字典的键进行排序，可以实现题目要求的返回的答案按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。
图解：

代码：

#
# return topK string
# @param strings string字符串一维数组 strings
# @param k int整型 the k
# @return string字符串二维数组
#
from collections import Counter 
class Solution:
    def topKstrings(self , strings , k ):
        # write code here
        result = Counter(strings)#利用Python的collection包下Counter的类，对各个字符串出现的次数进行统计，返回值是一个字典
        L = sorted(result.items(),key=lambda kv : (-kv[1], kv[0]))#先对字典按值降序排序，再按键进行升序排序
        L = L[:k]#切割列表，取得排序后的，排名前k的字符串及其次数
        return L

复杂度分析：
1、时间复杂度：sorted函数使用的是 Timesort 排序方法，最好情况下的时间复杂度是，平均情况以及最坏情况的时间复杂度是。
2、空间复杂度：sorted函数使用的Timesort排序方法，空间复杂度为。

解法二：
思路：
利用collections模块中counter类的函数most_common()，most_commom（）函数不传参数值时，用sort（）函数排序，排序的根据是以第2个元素数值进行排序的，返回的是从大到小的顺序的所有结果，如果有参数n,调用了 heapq模块中的 nlargest 函数返回的前n个的元素结果。
代码：

#
# return topK string
# @param strings string字符串一维数组 strings
# @param k int整型 the k
# @return string字符串二维数组
#
from collections import Counter
class Solution:
    def topKstrings(self , strings , k ):
        # write code here
        strings.sort()#先按字典排序
        return Counter(strings).most_common(k)#利用most_common取topk

复杂度分析：
1、时间复杂度：sort函数使用的是 Timesort 排序方法，最好情况下的时间复杂度是，平均情况以及最坏情况的时间复杂度是，most_common()函数的时间复杂度是，所以此解法时间复杂度是。
2、空间复杂度：sort函数使用的Timesort排序方法，空间复杂度为。