[LeetCode][Python]451. Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

問題解決の考え方:
まず、辞書を使うことです.keyは文字で、valueはその出現回数です.表示された回数でソートし、リストのextend操作を使用してkey*valueに接続します.
1.1 Pythonにはcollectionsモジュールがあり、値が何回発生したかを追跡するクラスCounterを提供しています.注意keyの出現順序はカウントに基づいて大きいものから小さいものまでである.その1つの方法most_common(n)はlistを返し、listにはCounterオブジェクトに最も多く現れる前のn要素が含まれています.
1.2 heapqモジュールには、nlargest()とnsmallest()の2つの関数があり、1つのセットから最大または最小のN要素のリストを取得できます.heapq.nlargest(n,heap)#クエリースタックの最大要素、nはクエリー要素の個数1.3 reduceを表す:reduce関数は簡略化され、反復するたびに前回の反復結果(最初はinitの要素、initがなければseqの最初の要素)を次の要素とともに2元のfunc関数を実行するプロセスである.reduce関数ではinitはオプションで、使用する場合は最初の反復の最初の要素として使用されます.
参照コード:

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import collections
import heapq
class Solution(object):
    def frequencySort1(self, s):
        """
        :type s: str
        :rtype: str
        """
        result = []
        for char, count in sorted(collections.Counter(s).items(), key=(lambda x:x[1]), reverse=True):
            result.extend([char]*count)
        return ''.join(result)

    def frequencySort2(self, s):
        return "".join([char*times for char, times in collections.Counter(s).most_common()])

    def frequencySort3(self, s):
        h = [(v, k) for k, v in collections.Counter(s).items()]
        return ''.join(v*k for v, k in heapq.nlargest(len(h), h))

    def frequencySort4(self, s):
        c = collections.Counter(s)
        return reduce(lambda a, b: b[1] * b[0] + a, sorted((c[i], i) for i in c), '')



if __name__ == '__main__':
    sol = Solution()
    s1 = "tree"
    s2 = 'cccaaa'
    s3 = 'Aabb'
    print sol.frequencySort1(s1)
    print sol.frequencySort1(s2)
    print sol.frequencySort1(s3)

    print '
'

    print sol.frequencySort2(s1)
    print sol.frequencySort2(s2)
    print sol.frequencySort2(s3)

    print '
'

    print sol.frequencySort3(s1)
    print sol.frequencySort3(s2)
    print sol.frequencySort3(s3)

    print '
'

    print sol.frequencySort4(s1)
    print sol.frequencySort4(s2)
    print sol.frequencySort4(s3)