[LeetCode] 451. Sort Characters By Frequency

轉自LeetCode

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.

<Solution>

參考解法

主要的想法是

• 先用一個 unordered_map 紀錄每個字元的頻率，key 是 char，value 是 frequency

    用 unordered_map 的原因是，不去打亂原本字母在字串裡出現的順序

• 再用一個 map ，key 是 frequency，value 是一個 vector<string> 來存字元

    用 vector<string> 來當value，是因為同一個頻率的字元，可能不只一個

    再用一個 map 並且拿 frequency 當 key 的原因是，map 會自動對 key 做升冪排序

    所以到時候逆向 iterate map，就可以從頻率最高的字元開始輸出

• 最後根據頻率，append 到最後的字串

c++

	class Solution {
	public:
	string frequencySort(string s) {
	string ansStr;
	unordered_map<char,int> freqMap;
	map<int,vector<char>> ansMap;
	//> count frequenct of character in string
	for(auto c : s) {
	freqMap[c]++;
	}
	//> put to Map : key is frequency, value is character
	//> Map will sort key automatically (increasing order)
	for(auto f : freqMap) {
	ansMap[f.second].push_back(f.first);
	}
	//> append character to string depends on its frequency
	for(auto it = ansMap.rbegin(); it != ansMap.rend(); ++it) {
	for(auto c : it->second) {
	ansStr.append(it->first, c);
	}
	}
	return ansStr;
	}
	};

view raw frequency.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun frequencySort(s: String): String {
	val map = mutableMapOf<Char,Int>()
	for(c in s) {
	map[c] = map[c]?.let {it+1} ?: 1
	}
	val results = map.toList()
	.sortedByDescending{it.second}
	.map{it -> Pair(it.second,it.first)}
	val sb = StringBuilder()
	for(r in results) {
	for(i in 0 until r.first) {
	sb.append(r.second)
	}
	}
	return sb.toString()
	}
	}

view raw sort_characters_by_frequency.kt hosted with ❤ by GitHub