[LeetCode][Python]451. Sort Char

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的出现顺序是根据计数的从大到小。它的一个方法most_common(n)返回一个list, list中包含Counter对象中出现最多前n个元素。

1.2 heapq模块有两个函数：nlargest() 和 nsmallest() 可以从一个集合中获取最大或最小的N个元素列表。heapq.nlargest (n, heap) #查询堆中的最大元素，n表示查询元素个数
1.3 reduce: reduce函数即为化简，它是这样一个过程：每次迭代，将上一次的迭代结果（第一次时为init的元素，如没有init则为seq的第一个元素）与下一个元素一同执行一个二元的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 '\n'

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

    print '\n'

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

    print '\n'

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