使用ArrayList、subList和contains方法高效查找并打印重复值

核心概念：基于子列表的重复值检测

在处理 ArrayList 中的数据时，我们有时需要识别并提取所有重复出现的元素。一种直观且易于理解的方法是结合使用 ArrayList 的 subList() 和 contains() 方法。其核心思想是：对于列表中的每一个元素，我们都去检查它是否在列表的“剩余部分”中再次出现。如果出现，则表明该元素是一个重复值。

具体步骤如下：

1. 遍历列表： 从列表的第一个元素开始，依次访问每个元素。
2. 创建子列表： 对于当前访问的元素（假设其索引为 i），我们创建一个从索引 i+1 到列表末尾的子列表。这个子列表代表了当前元素之后的所有元素。
3. 检查存在性： 使用 contains() 方法检查当前元素是否出现在这个子列表中。
4. 收集重复值： 如果 contains() 返回 true，则说明当前元素在列表的后续部分中至少重复出现了一次，因此它是一个重复值。为了确保结果列表中只包含唯一的重复值，我们还需要在添加之前检查它是否已经存在于结果集中。

实现细节与代码示例

下面是一个Java方法，它实现了上述逻辑，并返回一个包含所有唯一重复值的 ArrayList。

Eva Design System

基于深度学习的色彩生成器

86

查看详情

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

public class DuplicateFinder {

    /**
     * 使用ArrayList的subList()和contains()方法查找并返回列表中的唯一重复值。
     *
     * @param arrayList 待检查的整数列表。
     * @return 包含所有唯一重复值的ArrayList。
     */
    public static ArrayList<Integer> findDuplicates(ArrayList<Integer> arrayList) {
        // 用于存储找到的唯一重复值
        ArrayList<Integer> result = new ArrayList<>();

        // 遍历原始列表中的每一个元素
        for (int i = 0; i < arrayList.size(); i++) {
            Integer currentElement = arrayList.get(i); // 获取当前元素

            // 检查两个条件：
            // 1. 当前元素是否已经添加到结果集，以避免重复添加同一个重复值。
            // 2. 当前元素是否在当前索引之后的子列表中存在，这表明它是一个重复值。
            if (!result.contains(currentElement) && 
                arrayList.subList(i + 1, arrayList.size()).contains(currentElement)) {

                result.add(currentElement); // 如果两个条件都满足，则将其添加到结果集
            }
        }
        return result; // 返回包含所有唯一重复值的列表
    }

    public static void main(String[] args) {
        // 示例用法
        ArrayList<Integer> numList1 = new ArrayList<>(List.of(2, 3, 4, 4, 5));
        ArrayList<Integer> duplicates1 = findDuplicates(numList1);
        System.out.println("列表 " + numList1 + " 中的重复数字是: " + duplicates1); // 预期输出: [4]

        ArrayList<Integer> numList2 = new ArrayList<>(List.of(1, 2, 3, 1, 2, 4, 5, 5));
        ArrayList<Integer> duplicates2 = findDuplicates(numList2);
        System.out.println("列表 " + numList2 + " 中的重复数字是: " + duplicates2); // 预期输出: [1, 2, 5]

        ArrayList<Integer> numList3 = new ArrayList<>(List.of(1, 2, 3));
        ArrayList<Integer> duplicates3 = findDuplicates(numList3);
        System.out.println("列表 " + numList3 + " 中的重复数字是: " + duplicates3); // 预期输出: []

        ArrayList<Integer> numList4 = new ArrayList<>(List.of(7, 7, 7, 7));
        ArrayList<Integer> duplicates4 = findDuplicates(numList4);
        System.out.println("列表 " + numList4 + " 中的重复数字是: " + duplicates4); // 预期输出: [7]
    }
}

代码解析

• findDuplicates 方法：
  • 接收一个 ArrayList<Integer> 参数 arrayList，这是我们要检查的原始列表。
  • 初始化一个 ArrayList<Integer> result，用于存储最终找到的、不重复的重复值。
  • 外层 for 循环： for (int i = 0; i < arrayList.size(); i++) 遍历 arrayList 中的每一个元素。i 是当前元素的索引。
  • Integer currentElement = arrayList.get(i);： 获取当前索引 i 处的元素。
  • 条件判断 if (!result.contains(currentElement) && arrayList.subList(i + 1, arrayList.size()).contains(currentElement))：
    • !result.contains(currentElement)：这个条件非常重要，它确保我们只将每个唯一的重复值添加到 result 列表中一次。例如，如果列表是 [4, 4, 4]，当第一个 4 被识别为重复时，它会被添加到 result 中。当处理第二个 4 时，由于 result 已经包含 4，这个条件将为 false，从而避免重复添加。
    • arrayList.subList(i + 1, arrayList.size())：这会创建一个从当前元素 i 的下一个索引 (i + 1) 到列表末尾的子列表。subList 返回的是原始列表的一个视图，而不是一个全新的独立列表，这意味着它不会复制所有元素，因此在空间上是高效的。
    • .contains(currentElement)：在这个子列表中查找 currentElement。如果找到，则说明 currentElement 在其后续部分中至少重复出现了一次。
  • result.add(currentElement);： 如果上述两个条件都满足（即 currentElement 尚未被添加到 result 且它在列表的后续部分中存在），则将其添加到 result 列表中。
  • 最后，方法返回 result 列表。
• main 方法：
  • 提供了几个不同场景的 ArrayList 示例，包括有重复值、无重复值和多个重复值的列表。
  • 调用 findDuplicates 方法并打印结果，以演示其功能。

注意事项与性能考量

虽然这种方法直观易懂，但在实际应用中，尤其是在处理大型数据集时，需要考虑其性能特性：

• 时间复杂度： 这种方法的平均和最坏时间复杂度为 O(N^2)，其中 N 是 ArrayList 的大小。
  • 外层 for 循环执行 N 次。
  • 在每次循环中，arrayList.subList() 操作通常是 O(1)（因为它返回一个视图）。
  • 然而，subList().contains() 操作在最坏情况下需要遍历子列表，子列表的长度从 N-1 递减到 0。ArrayList 的 contains() 方法是一个线性搜索，其时间复杂度为 O(K)，其中 K 是子列表的长度。
  • 因此，总的时间复杂度是 N * O(N) = O(N^2)。
  • 此外，result.contains(currentElement) 同样是 O(K')，其中 K' 是 result 列表的长度，最坏情况下也接近 N，进一步增加了常数因子。
• 空间复杂度： 除了存储结果的 result 列表（最坏情况下为 O(N)）之外，subList() 方法返回的是原始列表的一个视图，不会创建新的底层数组，因此额外空间开销较小。
• 适用场景：
  • 当 ArrayList 的规模相对较小（例如，几百到几千个元素）时，这种方法的性能通常可以接受。
  • 当对代码的简洁性和直接使用 subList() 及 contains() 有明确要求时。
  • 作为理解 ArrayList 及其方法工作原理的教学示例。
• 替代方案： 对于需要处理大量数据且对性能要求极高的场景，通常会考虑更高效的算法：
  • 使用 HashSet： 可以通过遍历列表，将元素添加到 HashSet 中。如果 add() 方法返回 false（表示元素已存在），则该元素是重复的。这种方法的时间复杂度为 O(N)，因为 HashSet 的 add() 和 contains() 操作平均为 O(1)。
  • 先排序再查找： 对列表进行排序（O(N log N)），然后线性遍历已排序的列表，相邻元素相同的即为重复。这种方法的时间复杂度为 O(N log N)。

总结

结合使用 ArrayList 的 subList() 和 contains() 方法提供了一种直观的方式来查找列表中的重复元素。这种方法易于理解和实现，尤其适用于列表规模不大的情况。然而，在面对大规模数据集时，其 O(N^2) 的时间复杂度可能成为性能瓶颈，此时应考虑采用基于 HashSet 或排序等更高效的算法来优化解决方案。理解不同方法的优缺点，有助于在实际开发中做出明智的技术选择。

以上就是使用ArrayList、subList和contains方法高效查找并打印重复值的详细内容，更多请关注php中文网其它相关文章！