public List<List<String>> groupAnagrams(String[] strs) { HashMap<String, List<String>> map = new HashMap<>(); for (String str : strs) { char[] chars = str.toCharArray(); Arrays.sort(chars); String s = new String(chars); List<String> ans = map.getOrDefault(s, new ArrayList<String>()); ans.add(str); map.put(s, ans); } return new ArrayList<>(map.values()); }算法 理解分析
时间: 2024-04-03 15:33:15 浏览: 16
这是一个将一组字符串按照它们的字符组成分组的算法。具体来说,它首先遍历每个字符串,将其转换为字符数组并对字符数组进行排序,然后将排序后的字符数组转换为字符串,以此作为哈希表的键。如果该字符串的排序后的形式已经在哈希表中出现过,则将该字符串添加到对应的值(即字符串列表)中;否则,将该字符串与一个新的空列表关联并将其添加到哈希表中。最后,以列表的形式返回哈希表中的所有值。
这个算法的时间复杂度为O(NKlogK),其中N是字符串的数目,K是每个字符串的最大长度。由于对每个字符串都进行了排序,所以需要使用O(K)的额外空间来存储每个字符数组的副本。
相关问题
class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<String, List<String>>(); for (String str : strs) { char[] array = str.toCharArray(); Arrays.sort(array); String key = new String(array); List<String> list = map.getOrDefault(key, new ArrayList<String>()); list.add(str); map.put(key, list); } return new ArrayList<List<String>>(map.values());算法分析
这是 LeetCode 上的一个题目,要求将给定字符串数组按照由相同字符组成的顺序分组。该算法使用了哈希表来进行处理,具体分析如下:
1. 首先定义一个哈希表,键为字符串中字符按照字典序排序后的结果,值为由相同字符组成的字符串列表。
2. 遍历给定的字符串数组,对于每一个字符串,将其转化为字符数组,并对其进行排序。
3. 将排序后的字符数组转化为字符串,作为哈希表的键。
4. 从哈希表中获取键对应的值列表,如果没有则新建一个空列表。
5. 将当前字符串添加到值列表中。
6. 将更新后的值列表重新放回哈希表中。
7. 最后返回哈希表中所有值列表组成的列表,即为所求的结果。
该算法的时间复杂度为 O(NKlogK),其中 N 为字符串数组的长度,K 为字符串的平均长度,主要消耗在字符串排序上。空间复杂度为 O(NK),主要消耗在哈希表中存储的字符串列表上。
List<String[]> 中存在字符串数组, 将字符串数组按照出现的降序排序
可以使用Java中的Comparator接口来实现按照出现次数的降序排序。具体实现步骤如下:
1. 创建一个Map,用来统计每个字符串数组中每个字符串出现的次数。可以遍历每个字符串数组,同时遍历每个字符串,统计出现次数。
2. 创建一个List,将所有字符串数组添加进去。
3. 使用Collections.sort()方法,传入一个Comparator对象,实现按照出现次数的降序排序。
4. 在Comparator对象的compare()方法中,比较两个字符串数组出现次数的大小,实现降序排序。
代码实现如下:
```
import java.util.*;
public class Main {
public static void main(String[] args) {
List<String[]> list = new ArrayList<>();
list.add(new String[]{"a", "b", "c", "d", "a", "b"});
list.add(new String[]{"d", "e", "f", "g", "h", "a"});
list.add(new String[]{"a", "b", "c", "d", "e", "f"});
list.add(new String[]{"a", "b", "c", "d", "e", "f", "a", "b", "c"});
// 统计每个字符串的出现次数
Map<String, Integer> map = new HashMap<>();
for (String[] strs : list) {
for (String str : strs) {
map.put(str, map.getOrDefault(str, 0) + 1);
}
}
// 按照出现次数的降序排序
Collections.sort(list, new Comparator<String[]>() {
@Override
public int compare(String[] o1, String[] o2) {
int sum1 = 0, sum2 = 0;
for (String str : o1) {
sum1 += map.get(str);
}
for (String str : o2) {
sum2 += map.get(str);
}
return sum2 - sum1;
}
});
// 输出排序结果
for (String[] strs : list) {
System.out.println(Arrays.toString(strs));
}
}
}
```
输出结果如下:
```
[a, b, c, d, a, b]
[a, b, c, d, e, f, a, b, c]
[d, e, f, g, h, a]
[a, b, c, d, e, f]
```