目录

0. 磨叽一下

1. leetcode题目--返回前k 个出现次数最多的单词

2. 未领会题目精神的错误解答

3. python多条件排序 

0. 磨叽一下

刷leetcode有一阵子了，出于效率考虑，还只是把重点放在简单类型的题目，这个难度的题目花费时间不会太长，基本上利用每天到公司上班前的一小段时间可以完成一道。

但是总是停留着自己的舒适区是不会有太大的进步，于是也开始尝试一些中等难度的题目，这部分的问题思路会比较绕一些，对于用python语言编写的话，需要详细了解python中一些核心内嵌函数的用法。

废话不多说，直接上题目。

1. leetcode题目--返回前k 个出现次数最多的单词

给一非空的单词列表，返回前k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例 1：

输入:["i", "love", "leetcode", "i", "love", "coding"], k = 2输出:["i", "love"]解析:"i" 和 "love" 为出现次数最多的两个单词，均为2次。    注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

输入:["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4输出:["the", "is", "sunny", "day"]解析:"the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，    出现次数依次为 4, 3, 2 和 1 次。

注意：

假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。

输入的单词均由小写字母组成。

2. 未领会题目精神的错误解答

咋一看题目，感觉很简单，刷刷给出了答案：

class Solution:

    def topKFrequent(self, words, k):
        """
        思路如下：
        1.首先使用一个dict对象统计每个单词出现的频率以及出现的顺序；
        2.使用sorted函数，以词频为关键词进行排序，并截取前k个结果；
        3.在以单词出现的顺序排序，返回结果
        """
        word_map = {}
        for i in range(len(words)):
            if not word_map.get(words[i], 0):
                word_map[words[i]] = [1,i]
            else:
                word_map[words[i]][0] = word_map[words[i]][0] + 1
        result = list(map(lambda x: (x[0],x[1][1]), sorted(word_map.items(), key=lambda k: k[1][0], reverse=True)[:k]))
        print(result)
        return [i[0] for i in sorted(result,key=lambda x:x[1],reverse=False)]

一看测试结果傻眼了，果然有坑 。

输入：["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"] 4

输出：["the","day","is","sunny"]

预期：["the","is","sunny","day"]

3. python排序函数sorted之参数key

先使用词频为条件排序，然后再使用出现顺序排序，最后得到的结果实际并不是按照词频为第一排序条件，很明显对于多条件排序的理解并不是很到位，虽然明白想要的结果是什么样的，可自己实现后才发现没有想的那么简单。

以前没有使用过python3的多条件排序功能，于是找了相关文章参考：

• python 排序 sorted 如果第一个条件 相同 则按第二个条件排序
• python多条件排序 

python语言中多条件排序的方式使用很方便，在sorted函数中，指定形如：key=lambda x:(x[0],x[1]) 的多个关键字即可进行排序，对于不同的关键字正序、逆序方式，一个控制的小技巧就是在不同的字段前面根据需要添加一个负号（-）即可，如：

• key=lambda x:(x[0],x[1]) ，则会根据参数的第一个字段，第二个字段按照正序排列；
• key=lambda x:(x[0],-x[1]) ，则会根据参数的第一个字段正序，第二个字段按照逆序排列；

然而，知道了这种使用方式，依旧无法解决我们这个问题，这也体现了题目本身的魅力，绝不会简简单单就可以实现目的。

到这里，应该都发现了问题的所在，即根据词频排序很简单，只要将词频的属性作为排序条件就可以，但是怎么比较单词在字母表出现的顺序呢？

有人说这个问题简单，只要将两个单词一位一位去比较不久OK了。

想法没问题，问题在于，sorted函数的参数key是一个只能接收单个参数的回调函数对象，言下之意，你没有办法将两个单词作为参数传入从而一位一位比较，你只能传入一个单词的属性。

4. python2.7排序函数sorted之参数cmp

python2.7的sorted排序函数为sorted(iterable, key, cmp, reverse)，可以选择传入key，或者cmp函数的方式选择排序的比较方式。

cmp回调函数与key回调函数的主要区别在于其接收两个参数，并返回两个参数的比较值用于结果排序。

即可以这样写：

cmp=lambda x,y: x-y

注意其与key回调函数的区别！
有人要问，为什么这么麻烦，需要区分两种不同的回调函数。为了解释这个问题，先看看对象的唯一数值表示。

5. 哈希与对象的数值表示

多数人对哈希算法应该不会陌生，其原理就在于为一些语言中常见的对象赋予一个唯一值，以字符串为例，为了比较两个字符串是否相等，常规的做法是一个个字符比较，另一种方式就是先计算字符串的哈希值，然后比较哈希值是否相等即可比较字符串是否相等。哈希值可以用于比较的一个重要愿意在于，哈希值的编码范围非常大，以常见的md5哈希算法为例，其使用128位进行编码，因此可以表示个编码，对于常规的处理，这么大的数值足以满足需求，不同的对象产生相同哈希值的概率非常低，除非对象的数量达到这样一个数量级。

很多情况下，我们其实用不着哈希值比较，比如简单的数值比较，或者字符串的长度比较。

但有时候我们的比较不会那么简单，例如上述题目中对于单词字母顺序的比较，情况就比较复杂。为了比较字符串出现的顺序，假如选择对其字符串进行编码，以10000个长度的字符串为例（假设全部为小写字母），每个字符有26种取值，那么10000个字符所需要的编码为，这是一个非常大的数字，仅仅为了比较一个字符串就使用这么大的数值，非常不划算。

假如换一种方式，使用两个字符串直接比较，那么情况会简单很多，只需要一位一位逐次比较即可实现目的。

回到上面的话题，可以理解为使用key回调函数就类似于使用绝对编码的方式进行比较；而使用cmp回调函数的方式就类似于使用直接比较的方式进行比较。

6. python3中使用cmp函数的方式

由于python3中把sorted函数中cmp参数移除，仅保留一个key参数，那么是不是意味着没有办法使用cmp参数的方式进行排序呢？并非如此，设计者早就考虑到了这一点，为了在sorted函数中使用cmp回调函数，可以使用 functools.cmp_to_key() 这样一个方法进行转换。

于是回到最开始，继续我们这个题目的解决。

import functools

class Solution:
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        word_map = {}
        for i in range(len(words)):
            if not word_map.get(words[i], 0):
                word_map[words[i]] = 1
            else:
                word_map[words[i]] = word_map[words[i]] + 1
        sort_by_letter = sorted(word_map.items(), key=functools.cmp_to_key(self.asc_cmp))
        print(sort_by_letter)
        sort_by_count = sorted(sort_by_letter, key=lambda x:-x[1])[:k]
        return [i[0] for i in sort_by_count]

    def asc_cmp(self, a, b):
        first,second=a[0],b[0]
        for i, j in zip(first, second):
            if i == j:
                continue
            else:
                return ord(i) - ord(j)
        return len(first) - len(second)

好了，提交答案，顺利通过！

扯了这么多，其实就是想说明一点，解决问题的过程比结果更重要，如何一步步去思考解决问题的思路，才是我们学习算法想要锻炼的能力！

最后

以上就是如意过客为你收集整理的Leetcode前k个出现次数最多的单词--对python3排序函数的思考 0. 磨叽一下1. leetcode题目--返回前k 个出现次数最多的单词2. 未领会题目精神的错误解答3. python排序函数sorted之参数key4. python2.7排序函数sorted之参数cmp5. 哈希与对象的数值表示6. python3中使用cmp函数的方式的全部内容，希望文章能够帮你解决Leetcode前k个出现次数最多的单词--对python3排序函数的思考 0. 磨叽一下1. leetcode题目--返回前k 个出现次数最多的单词2. 未领会题目精神的错误解答3. python排序函数sorted之参数key4. python2.7排序函数sorted之参数cmp5. 哈希与对象的数值表示6. python3中使用cmp函数的方式所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。