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.
Python Solution 1: [Heap]
class Solution(object):
def frequencySort(self, s):
freq = collections.Counter(s)
freq_list = [(-freq[c], c) for c in freq]
heapq.heapify(freq_list)
res = []
while freq_list:
count, c = heapq.heappop(freq_list)
res.extend([c] * -count)
return "".join(res)
Python Solution 2: [Bucket]:
class Solution(object):
def frequencySort(self, s):
freq = collections.Counter(s)
count = {}
for c in freq:
if freq[c] not in count:
count[freq[c]] = []
count[freq[c]].append(c * freq[c])
return "".join(["".join(count[i]) for i in range(len(s), -1, -1) if i in count])
Python Solution 3:
class Solution(object):
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
d = collections.Counter(s)
d = [(d[val], val) for val in d]
d.sort(reverse = True)
return ''.join(val * count for count, val in d)
Python Solution 4:
class Solution(object):
def frequencySort(self, s):
"""
:type s: str
:rtype: str
"""
d = collections.Counter(s)
res = sorted(d.items(), key = lambda x: x[1], reverse = True)
return ''.join([c * count for c, count in res])
Summary:
- Got use to Pythonic
LeetCode: 451. Sort Characters By Frequency
近期评论