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)
