Anagram 指由颠倒字母顺序而构成的单词。
e.g. 给出 ["eat", "tea", "tan", "ate", "nat", "bat"]，假设所给单词仅由小写字母组成。
返回
[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
我的算法原理是 key - value，但不会使用 map，所以效率极低。
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> result;
vector<string> key;
for (string str : strs) {
string s = str;
sort(s.begin(), s.end());
vector<string>::iterator it = find(key.begin(), key.end(), s);
if (it == key.end()) {
key.push_back(s);
result.push_back({str});
} else {
result[it - key.begin()].push_back(str);
}
}
return result;
}
看到别人一种算法原理和我完全一样，但使用了 unordered_map 和 multiset，效率大大提高。
unordered_map 不会根据 key 的大小进行排序，存储时是根据 key 的 hash 值判断元素是否相同。因此如果存放自定义类型，那么就需要重载 operator== 以及 hash_value 函数。
multiset 是 <set> 库中一个非常有用的类型。set 的特性是所有元素都会根据值自动排序；set 不允许两个元素拥有相同的值；不能通过迭代器修改 set 元素的值。
set 和 multiset 都是基于红黑树实现的，因此元素在插入 / 删除的过程中就实现了排序，不同的是后者允许元素重复而前者不允许。
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, multiset<string>> mp;
for (string s : strs) {
string t = s;
sort(t.begin(), t.end());
mp[t].insert(s);
}
vector<vector<string>> anagrams;
for (auto m : mp) {
vector<string> anagram(m.second.begin(), m.second.end());
anagrams.push_back(anagram);
}
return anagrams;
}
由于条件 “所给单词仅由小写字母组成”，将 O(nlogn) 的 sort 换成基于 counting sort （O(n)时间）的排序函数，也会提高一定效率。
vector<vector<string>> groupAnagrams(vector<string>& strs) {
...
string t = strSort(s);
...
}
string strSort(string& s) {
int count[] = {}, n = s.length();
for (int i = ; i < n; i++)
count[s[i] - 'a']++;
int p = ;
string t(n, 'a');
for (int j = ; j < ; j++)
for (int i = ; i < count[j]; i++)
t[p++] += j;
return t;
}
计数排序是一个非基于比较的排序算法，它的优势在于在对一定范围内的整数（即输入的线性表元素属于有限偏序集）排序时，它的复杂度为 Ο(n+k)（其中 k 是整数的范围），快于任何比较排序算法，但当 O(k) > O(nlogn) 时其效率不如比较排序。这是一种牺牲空间换取时间的做法。
算法思想：扫描整个序列，对每一个元素 x，确定该序列中值小于等于 x 的元素的个数。如果输入序列中只有 17 个元素的值小于等于 x 的值，则 x 可以直接存放在输出序列的第 18 个位置上。如果有重复元素时，我们不能将这些元素放在输出序列的同一个位置上，因此还要作适当的修改。