将列表中相似项分组到字典中, 学习列表和字典的操作（Java范型写法）

问题描述

将列表中出现的相似项分组到字典中，比如列表['apple','orange', 'apple','pear','pear']，

需要将出现的相似项分组到字典中，字典的key是列表中的项，value是出现的索引

并且需要支持根据出现次数进行结构的筛选，比如只有出现次数大于1的项才会被分组到字典中

测试代码

List<String> fruits = List.of("apple", "orange", "apple", "pear", "pear");
Map<String, List<Integer>> result = groupSimilar(fruits, 1);
assertEqual(result.size(), 2, "1");
assertEqual(result.get("apple").size(), 2, "2");
assertEqual(result.get("pear").size(), 2, "3");

解决思路

这个需求其实是非常简单的遍历列表的需求，过程中为了保证效率，需要使用一个字典来存储已经出现的项，然后遍历列表，将出现的项存储到字典中。

如果结果不用字典，直接使用列表来存储，那么每次遍历列表的时候，都需要遍历一遍列表来判断是否已经出现过，这样的效率是非常低的，算法的时间复杂度是O(n^2)。

遍历列表，每个项查看是否在字典中，如果在字典中，将索引添加到字典的值中
如果不在字典中，将项添加到字典中，值是一个列表，存储索引。
最后根据出现次数进行筛选，只有出现次数大于N的项才会被分组到字典中。

代码实现

 public static <T> Map<T, List<Integer>> groupSimilar(List<T> items, int threshold) {
     Map<T, List<Integer>> groups = new HashMap<>();
     for (int idx = 0; idx < items.size(); idx++) {
         T item = items.get(idx);
         groups.computeIfAbsent(item, k -> new ArrayList<>()).add(idx);
     }

     if (threshold > 0) {
         groups.values().removeIf(list -> list.size() < threshold);
     }
     return groups;
 }

代码解析

这个需求其实是非常简单的遍历列表的需求, 我们选择了用范型的方式实现，这样可以适配更多的数据类型，比如String，Integer等。

我们使用了一个HashMap来存储已经出现的项，然后遍历列表，将出现的项存储到字典中。
采用了computeIfAbsent方法来实现，如果字典中没有这个项，就创建一个新的列表，然后将索引添加到列表中。
最后根据出现次数进行筛选，只有出现次数大于N的项才会被分组到字典中。

如果要安全的循环过程中移除元素，需要使用迭代器来进行操作，比如不能用下面的方式来删除元素：

for (Map.Entry<T, Integer> entry : groups.entrySet()) {
    if (entry.getValue() < threshold) {
        // ⚠️ 不能用这种方式删除元素
        groups.remove(entry.getKey()); // ❌ 
    }
}

在一个循环中，不能同时对一个集合进行增删操作，否则会抛出ConcurrentModificationException异常。

必须用迭代器来进行操作，这样可以保证在遍历的时候，可以安全的删除元素。我们选择了使用removeIf方法来进行删除操作。

完整代码请参考: Similar.java

总结

Java通过范型可以提升代码的复用性，大家一定要学习好范型
HashMap是常用并且效率非常高的一个容器，通过HashMap可以实现很多的功能，比如计数，分组等
如果要循环操作一个集合，并且在循环中删除元素，一定要使用迭代器来进行操作，否则会抛出ConcurrentModificationException异常。
Java的集合类提供了很多的方法来进行操作，比如computeIfAbsent，removeIf等，大家一定要熟练掌握。这些可以减少很多的代码量，提高代码的可读性。

所有的后端面试常见的问题，我们每天都会在我们的编程群里面讨论和Code review, 欢迎大家加入我们的编程群，一起学习和进步。

编程交流群

欢迎大家关注入职啦 (公众号: ruzhila) ，获取更多有趣的编程挑战题和技术干货！