问题描述

测试代码

解决思路

代码实现

代码解析

总结

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

小葵

2024-06-28

🏷

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)。

  1. 遍历列表,每个项查看是否在字典中,如果在字典中,将索引添加到字典的值中
  2. 如果不在字典中,将项添加到字典中,值是一个列表,存储索引。
  3. 最后根据出现次数进行筛选,只有出现次数大于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等。

  1. 我们使用了一个HashMap来存储已经出现的项,然后遍历列表,将出现的项存储到字典中。
  2. 采用了computeIfAbsent方法来实现,如果字典中没有这个项,就创建一个新的列表,然后将索引添加到列表中。
  3. 最后根据出现次数进行筛选,只有出现次数大于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的集合类提供了很多的方法来进行操作,比如computeIfAbsentremoveIf等,大家一定要熟练掌握。 这些可以减少很多的代码量,提高代码的可读性。

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

编程交流群

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

友情链接:

Copyright© 2024 杭州园中葵科技有限公司 版权所有