基于相同字段合并两列表并递增studentList2的id的优化方案咨询

需求：现有两个结构一致的学生列表studentList1和studentList2，部分学生在不同国家拥有两处住所。合并两列表时，需将studentList2的ID字段基于studentList1的最大ID进行递增处理，要替代低效的双重循环实现。

原始数据 #

studentList1：

schoolId | id | countryCode | cityCode
5555       1      20            1
5555       1      24            2
5555       2      1             3
5555       3      1             3
5555       4      1             3

studentList2：

schoolId | id | countryCode | cityCode
6666       1      20            1
6666       1      24            2
6666       2      20            1
6666       2      24            2
6666       3      20            1
6666       3      24            2
6666       4      20            1
6666       4      24            2
6666       5      1             3
6666       6      1             3

预期合并结果：

schoolId | id | countryCode | cityCode
5555       1      20            1
5555       1      24            2
5555       2      1             3
5555       3      1             3
5555       4      1             3
6666       5      20            1
6666       5      24            2
6666       6      20            1
6666       6      24            2
6666       7      20            1
6666       7      24            2
6666       8      20            1
6666       8      24            2
6666       9      1             3
6666       10     1             3

优化方案 #

双重循环的时间复杂度是O(n*m)，数据量大时效率极低。下面的方案时间复杂度为O(n + m)，更高效：

步骤1：获取studentList1的最大ID

先找出第一个列表里的最大ID，作为第二个列表ID递增的起点。以Java为例：

// 假设Student类有getId()方法
int maxId = studentList1.stream()
    .mapToInt(Student::getId)
    .max()
    .orElse(0); // 空列表时默认从0开始

步骤2：建立原始ID到新ID的映射

用HashMap记录第二个列表中每个原始ID对应的新ID，确保同一原始ID的所有记录用同一个新ID：

Map<Integer, Integer> idMap = new HashMap<>();
int currentNewId = maxId;
for (Student s : studentList2) {
    // 如果原始ID未映射过，生成新ID并赋值
    idMap.computeIfAbsent(s.getId(), k -> ++currentNewId);
}

步骤3：替换ID并合并列表

遍历第二个列表，替换ID后加入合并结果：

List<Student> mergedList = new ArrayList<>(studentList1);
for (Student s : studentList2) {
    // 复制原对象并替换ID
    Student newStudent = new Student(
        s.getSchoolId(),
        idMap.get(s.getId()),
        s.getCountryCode(),
        s.getCityCode()
    );
    mergedList.add(newStudent);
}

方案说明 #

• 这个方案只需要遍历两个列表各一次，加上一次映射表的构建，整体效率远高于双重循环。
• 确保了studentList2中同一原始ID的学生记录，合并后ID保持一致，符合需求。

内容的提问来源于stack exchange，提问作者tom