推 oin1104: 大師 02/07 13:23
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: https://leetcode.com/problems/sort-characters-by-frequency/description
: 451. Sort Characters By Frequency
: 給你一個字串s，把他的所有字元依照出現次數降序排列，如果答案有多個返回任意一個
: 思路：
: 1.先數s的每個字元有幾個
: 2.把s數量大於0的字元(計數索引)丟到MaxHeap依照數量排序
: 3.不斷從Heap取出字元並append成一個字串即可
Python3 code:
------------------------------------------------
from collections import Counter
class Solution:
def frequencySort(self, s: str) -> str:
return ''.join(_[0] * _[1] for _ in Counter(s).most_common())
------------------------------------------------
第一解 用Counter查出每個字元的數量 再用most_common回傳順序
------------------------------------------------
from collections import defaultdict
class Solution:
def frequencySort(self, s: str) -> str:
f = defaultdict(int)
for char in s:
f[char] += 1
sorted_s = sorted(f.keys(), key=lambda x: f[x], reverse=True)
return ''.join(char * f[char] for char in sorter_s)
------------------------------------------------
問ChatGPT說Counter會多用額外的空間 所以就改用dict記錄
------------------------------------------------
from collections import defaultdict
class Solution:
def frequencySort(self, s: str) -> str:
(f := defaultdict(list)) or [f[char].append(1) for char in s]
return ''.join(char * sum(f[char]) for char in sorted(f, key=lambda x: f[x], reverse=True)
------------------------------------------------
想用一行處理f就改成這樣 不過因為int是不可變 所以改用了list 乘的時候用sum()
不過空間複雜度就上升了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.251.103 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707282268.A.83A.html