leetcode hot100刷题日记——2.字母异位词分组
涉及知识点:vector、哈希表
- 解答
- 我的解答的时间复杂度分析
- 我的解答的空间复杂度分析
- 复习：排序算法的时间复杂度
和第一题需要的知识点相同，所以知识点复习可见 link1《leetcode hot100刷题日记——1.两数之和》
解题思路：是字母异位词的字符串的组成字母是相同的，所以可以对从strs取出来的字符串按照字母顺序排序，并作为hash表唯一的key。如果是字母异位词，那就放在一个key里。
解答
class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {//建立一个哈希表，哈希表的key是字母串（按照字母顺序排序），value是和字母串字母相同的数组元素unordered_map<string,vector<string>>map;for(string &str:strs){string sorted=str;sort(sorted.begin(),sorted.end());//这里要注意一下字符串内部的字母是咋排序的map[sorted].push_back(str);}vector<vector<string>> res;for(auto &m:map){res.push_back(m.second);//first，second联想一下}return res;}
};
我的解答的时间复杂度分析
- 遍历字符串数组：需要对输入的字符串数组进行一次完整遍历，时间复杂度为 O(n)，其中 n 是字符串的数量。
- 排序每个字符串：对每个字符串进行排序的时间复杂度取决于字符串的长度 k。对于每个字符串，排序的时间复杂度为 O(klogk)。因此，对于所有 n 个字符串，总时间复杂度为 O(n⋅klogk)。
- 遍历哈希表构建结果：遍历哈希表并将每个分组添加到结果列表的时间复杂度为 O(m⋅l)，其中 m 是哈希表中键值对的数量（即不同字母组合的数量），l 是每个分组的平均字符串数量。在最坏情况下，所有字符串互为不同变位词，此时 m=n 且 l=1，总时间复杂度为 O(n)。
- 综上，整个算法的时间复杂度为 O(n⋅klogk)，其中 k 是字符串的平均长度，主导因素为排序操作的耗时。
我的解答的空间复杂度分析
- 哈希表：哈希表需要存储每个排序后的字符串作为键，以及对应的原始字符串列表作为值。
每个键的长度为 k，假设所有键的总数为 m，键的总空间为 O(m⋅k)；
每个值存储原始字符串列表，所有值的总空间为 O(n⋅k)（所有原始字符串的总长度）。 - 结果列表：结果列表中包含所有字符串，总空间为 O(n⋅k)。
因此，整个算法的空间复杂度为 O(n⋅k+m⋅k)。在最坏情况下（所有字符串互为不同变位词），m=n，空间复杂度为 O(n⋅k)；在最优情况下（所有字符串为同一变位词），m=1，空间复杂度仍为 O(n⋅k)。
复习：排序算法的时间复杂度
| 排序算法 | 最好情况时间复杂度 | 平均情况时间复杂度 | 最坏情况时间复杂度 |
|---|---|---|---|
| 冒泡排序 (Bubble Sort) | O(n) | O(n^2) | O(n^2) |
| 选择排序 (Selection Sort) | O(n^2) | O(n^2) | O(n^2) |
| 插入排序 (Insertion Sort) | O(n) | O(n^2) | O(n^2) |
| 希尔排序 (Shell Sort) | O(nlogn) | O(n^1.25) | O(n^2) |
| 归并排序 (Merge Sort) | O(nlogn) | O(nlogn) | O(nlogn) |
| 快速排序 (Quick Sort) | O(nlogn) | O(nlogn) | O(n^2) |
| 堆排序 (Heap Sort) | O(nlogn) | O(nlogn) | O(nlogn) |
| 计数排序 (Counting Sort) | O(n+k) | O(n+k) | O(n+k) |
| 桶排序 (Bucket Sort) | O(n+k) | O(n+k) | O(n^2) |
| 基数排序 (Radix Sort) | O(n⋅k) | O(n⋅k) | O(n⋅k) |