python中自定义排序函数

2021-05-27 约 916 字预计阅读 2 分钟

不从算法层面讨论，而看看python实现上怎么写。

现有字典 d= {‘a’:24,‘g’:52,‘i’:12,‘k’:33}请按value值进行排序?

1

sorted(d.items(),key=lambda x:x[1])

前K个高频单词 (规则1下比较相同时，按照规则2排序)

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        count = {}
        for w in words:
            if w in count:
                count[w] += 1
            else:
                count[w] = 1
        count = sorted(count.items(), key = lambda kv:( - kv[1], kv[0])) # 排序的关键代码
        return [x[0] for x in count[:k]]

函数cmp_to_key

另外如果不是像数字排序或者字符串排序时，应自己定义cmp_to_key，如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


from collections import Counter
from functools import cmp_to_key
class Solution:
    def topKFrequent(self, words, k):
        d = Counter(words)

        def cmp(x, y):
            if d[x] > d[y] or (d[x] == d[y] and x < y):
                return -1
            else:
                return 1

        return sorted(d.keys(), key=cmp_to_key(cmp))[:k]

作者：qingfengpython
链接：https://leetcode-cn.com/problems/top-k-frequent-words/solution/692qian-kge-gao-pin-dan-ci-pythonshuang-eqc94/

还有一道cmp_to_key的题目是179. 最大数。

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


# 输入：nums = [10,2]
# 输出："210"
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        str_list = list(map(str, nums))
        compare = lambda x, y : 1 if x + y < y + x else -1
        str_list.sort(key = functools.cmp_to_key(compare))
        res = ''.join(str_list)
        if res[0] == '0':
            return '0'
        return res

重写堆排序规则

题目是前k个，所以可以用堆来优化。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


import heapq, collections
class Word:
    def __init__(self, word, fre):
        self.word = word
        self.fre = fre
    def __lt__(self, other):
        if self.fre != other.fre:
            return self.fre < other.fre
        return self.word > other.word

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        cnt = collections.Counter(words)
        heap = []
        for word, fre in cnt.items():
            heapq.heappush(heap, Word(word, fre))
            if len(heap) > k:
                heapq.heappop(heap)

        heap.sort(reverse=True)
        return [x.word for x in heap]

作者：luo-bi-da-quan
链接：https://leetcode-cn.com/problems/top-k-frequent-words/solution/pythonyou-xian-dui-lie-by-luo-bi-da-quan-w8me/

排序链表

ref. https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/

目录