Given a string, sort it in decreasing order based on the frequency of characters.
my answer
class Solution:
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
checked = []
count = []
for i in range(len(s)):
if s[i] not in checked:
checked.append(s[i])
count.append(1)
else:
count[checked.index(s[i])] += 1
for j in range(1, len(checked)): # ins_sort
while j > 0 and count[j-1] < count[j]:
count[j-1], count[j] = count[j], count[j-1]
checked[j-1], checked[j] = checked[j], checked[j-1]
j -= 1
result = []
for k in range(len(checked)):
result.append(checked[k] * count[k])
return ''.join(result) # list-->str
''.join(result):将result列表内的元素以‘’为连接符进行连接，返回字符串
用了插入排序对统计的词频进行排序
other's answer
def frequencySort(self, s):
result = []
for letter, times in sorted(Counter(s).iteritems(), key = lambda x: x[1], reverse = True):
result += [letter] * times
return ''.join(result)
Counter(s)返回一个key为被统计对象，value为对应词频的dict
字典的几种形式:
>>> a = dict(one=1, two=2, three=3)
>>> b = {'one': 1, 'two': 2, 'three': 3}
>>> c = dict(zip(['one', 'two', 'three'], [1, 2, 3]))
>>> d = dict([('two', 2), ('one', 1), ('three', 3)]) # 可以用d[0][0]和d[0][1]来对key和value进行访问
>>> e = dict({'three': 3, 'one': 1, 'two': 2})
- Counter(s).iteritems()：这是python2的方法，python3中用items()来实现,以上面的d的形式返回key和value
