java 两个list 里面对象相同，比如学生对象，相同id的学生的成绩进行累加再返回，不用双重循环O(N^2)复杂度如何实现？lambda如何实现？

Question

java 两个list 里面对象相同，比如学生对象，相同id的学生的成绩进行累加再返回，不用双重循环O(N^2)复杂度如何实现？lambda如何实现？

Answer 1

两个思路吧

1. 空间换时间，利用map，空间复杂度n，时间也是n

public class Test {
    public static void main(String[] args) {
        List<Student> list1 = new LinkedList<>();
        List<Student> list2 = new LinkedList<>();

        Map<String, Student> map = list1.stream().collect(Collectors.toMap(Student::getId, Function.identity()));
        for (Student student : list2) {
            Student other = map.get(student.getId());
            student.score += other == null ? 0 : other.score;
        }
    }

    class Student {
        String id;
        float score;

        public String getId() {
            return id;
        }
    }
}

1. 不想空间换时间，那也有办法简化到 nlogn，先都排序，然后双指针，大概是：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        // 注意双指针要用 ArrayList，不然性能很差
        List<Student> list1 = new ArrayList<>();
        List<Student> list2 = new ArrayList<>();

        Comparator<Student> comparator = Comparator.comparing(Student::getId);
        list1.sort(comparator);
        list2.sort(comparator);
        
        int p1 = 0, p2 = 0, len1 = list1.size(), len2 = list2.size();
        while (p1 < len1 && p2 < len2) {
            Student s1 = list1.get(p1);
            Student s2 = list2.get(p2);
            int com = s1.getId().compareTo(s2.getId());
            if (com == 0) {
                // 是同一个
                s1.score += s2.score;
                p1++;
                p2++;
            } else if (com < 0) {
                p1++;
            } else {
                p2++;
            }
        }
    }

    class Student {
        String id;
        float score;

        public String getId() {
            return id;
        }
    }
}