Java List 差集|极客笔记

Java List 差集

1. 简介

在 Java 编程中，我们经常会使用 List（列表）这种数据结构来存储一组元素。List 是一个有序的集合，允许重复元素的存在。有时候，我们需要对两个列表进行比较，找出它们之间的差异。本文将介绍如何使用 Java 的 List 来获取两个列表的差集。

2. 什么是差集

差集也叫做补集，是指两个集合中不相同的元素所组成的新集合。例如，假设有两个列表 A 和 B：

List<Integer> listA = Arrays.asList(1, 2, 3, 4, 5);
List<Integer> listB = Arrays.asList(4, 5, 6, 7, 8);

那么列表 A 和列表 B 的差集是指只存在于其中一个列表中的元素。在本例中，差集为 [1, 2, 3, 6, 7, 8]。

3. 方法一：使用 for 循环和 contains 方法

一种简单直观的方法是使用 for 循环和 contains 方法来逐个比较元素。具体步骤如下：

创建一个新列表，用于存储差集的元素。
遍历列表 A 的每个元素。
对于列表 A 中的每个元素，使用 contains 方法判断是否在列表 B 中存在。
如果不存在，则将该元素添加到新列表中。
重复步骤2-4，遍历列表 B 的每个元素。
返回新列表作为差集。

下面是使用这种方法来求差集的 Java 代码示例：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ListDifferenceExample {

    public static <T> List<T> getDifference(List<T> listA, List<T> listB) {
        List<T> difference = new ArrayList<>();

        for (T element : listA) {
            if (!listB.contains(element)) {
                difference.add(element);
            }
        }

        for (T element : listB) {
            if (!listA.contains(element)) {
                difference.add(element);
            }
        }

        return difference;
    }

    public static void main(String[] args) {
        List<Integer> listA = Arrays.asList(1, 2, 3, 4, 5);
        List<Integer> listB = Arrays.asList(4, 5, 6, 7, 8);

        List<Integer> difference = getDifference(listA, listB);
        System.out.println("差集：" + difference);
    }
}

运行结果如下：

差集：[1, 2, 3, 6, 7, 8]

通过遍历列表 A 和列表 B 的元素，并使用 contains 方法来判断是否存在在另一个列表中，我们可以得到两个列表的差集。

这种方法的时间复杂度为 O(n^2)，其中 n 是两个列表中元素的总数。由于 contains 方法的时间复杂度也为 O(n)，所以总的时间复杂度是两层循环的乘积。

4. 方法二：使用 removeAll 方法

除了使用循环和 contains 方法来获取差集，Java 的 List 类中还提供了一个方便的方法 removeAll，它可以删除列表中与指定集合相同的元素。我们可以使用这个方法来获取差集。

具体步骤如下：

创建一个新列表，用于存储差集的元素。
将列表 A 的所有元素添加到新列表中。
调用 removeAll 方法，传入列表 B，以删除新列表中与列表 B 相同的元素。
返回新列表作为差集。

下面是使用 removeAll 方法来求差集的 Java 代码示例：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ListDifferenceExample {

    public static <T> List<T> getDifference(List<T> listA, List<T> listB) {
        List<T> difference = new ArrayList<>(listA);
        difference.removeAll(listB);

        return difference;
    }

    public static void main(String[] args) {
        List<Integer> listA = Arrays.asList(1, 2, 3, 4, 5);
        List<Integer> listB = Arrays.asList(4, 5, 6, 7, 8);

        List<Integer> difference = getDifference(listA, listB);
        System.out.println("差集：" + difference);
    }
}

运行结果如下：

差集：[1, 2, 3]

通过将列表 A 的所有元素添加到新列表中，然后调用 removeAll 方法来删除与列表 B 相同的元素，我们可以得到两个列表的差集。

使用 removeAll 方法的时间复杂度为 O(m * n)，其中 m 和 n 分别是列表 A 和列表 B 中元素的个数。虽然比循环和 contains 方法要快一些，但仍然是两层循环的乘积。

5. 方法三：使用 Java 8 的 Stream API

从 Java 8 开始，引入了新的 Stream API，提供了函数式编程的特性。使用 Stream API，我们可以更简洁地获取差集。

具体步骤如下：

创建一个新列表，用于存储差集的元素。
调用 stream 方法将列表 A 转换为流。
调用 filter 方法，传入一个 Lambda 表达式，过滤掉列表 B 中的元素。
调用 collect 方法，将流中的元素收集到新列表中。
重复步骤2-4，对列表 B 进行同样的操作。
返回新列表作为差集。

下面是使用 Stream API 来求差集的 Java 代码示例：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class ListDifferenceExample {

    public static <T> List<T> getDifference(List<T> listA, List<T> listB) {
        List<T> difference = listA.stream()
                .filter(element -> !listB.contains(element))
                .collect(Collectors.toList());

        difference.addAll(listB.stream()
                .filter(element -> !listA.contains(element))
                .collect(Collectors.toList()));

        return difference;
    }

    public static void main(String[] args) {
        List<Integer> listA = Arrays.asList(1, 2, 3, 4, 5);
        List<Integer> listB = Arrays.asList(4, 5, 6, 7, 8);

        List<Integer> difference = getDifference(listA, listB);
        System.out.println("差集：" + difference);
    }
}

运行结果如下：