如何在 Java 中检查数组是否有重复元素

简介

在这个实验中，你将学习如何使用不同的方法在 Java 中检查数组是否包含重复元素。我们将从使用嵌套循环的基本方法开始，这种方法能让你清晰地理解比较过程。

接下来，我们将探索一种更高效的技术，即利用 HashSet 数据结构，展示如何借助 Java 集合来更快地检测重复元素。最后，我们将研究对数组进行排序如何简化识别重复元素的过程。在这个实验结束时，你将掌握多种处理 Java 数组中重复元素的策略。

Skills Graph

使用嵌套循环查找重复元素

在这一步中，我们将探索一种在 Java 中使用嵌套循环查找数组内重复元素的基本方法。这种方法简单直接、易于理解，是学习数组操作和基本算法设计的良好起点。

首先，在你的 ~/project 目录下创建一个名为 FindDuplicatesNested.java 的新 Java 文件。你可以直接在 WebIDE 文件资源管理器中，右键点击 project 文件夹，选择“新建文件”，然后输入文件名来完成此操作。

现在，在代码编辑器中打开 FindDuplicatesNested.java 文件，并添加以下 Java 代码：

public class FindDuplicatesNested {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        System.out.println("Finding duplicate elements using nested loops:");

        // Use nested loops to compare each element with every other element
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                // If a duplicate is found (elements are equal and not the same element)
                if (numbers[i] == numbers[j]) {
                    System.out.println("Duplicate found: " + numbers[j]);
                }
            }
        }
    }
}

让我们来分析一下这段代码：

• int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};：这行代码声明了一个名为 numbers 的整数数组，并使用一些值对其进行初始化，其中包含重复元素。
• for (int i = 0; i < numbers.length; i++)：这是外层循环。它使用索引 i 遍历数组中的每个元素。
• for (int j = i + 1; j < numbers.length; j++)：这是内层循环。对于索引 i 处的每个元素，它从索引 i 之后的元素开始遍历数组中 剩余的 元素。这一点很重要，这样可以避免将一个元素与自身进行比较，也可以避免两次找到同一对重复元素（例如，先比较索引 1 和索引 4，然后又比较索引 4 和索引 1）。
• if (numbers[i] == numbers[j])：这个条件检查索引 i 处的元素是否等于索引 j 处的元素。如果相等，就意味着我们找到了一个重复元素。
• System.out.println("Duplicate found: " + numbers[j]);：如果找到重复元素，这行代码会打印一条消息，指出该重复元素。

按下 Ctrl + S（在 macOS 上是 Cmd + S）保存文件。

现在，打开 WebIDE 底部的终端。确保你位于 ~/project 目录下。你可以通过输入 pwd 并按下回车键来确认。输出应该是 /home/labex/project。

使用 javac 命令编译 Java 代码：

javac FindDuplicatesNested.java

如果没有错误，编译将成功，并且会在 ~/project 目录下创建一个 FindDuplicatesNested.class 文件。你可以通过输入 ls 并按下回车键来验证。

最后，使用 java 命令运行编译后的 Java 程序：

java FindDuplicatesNested

你应该会看到程序输出的找到的重复元素。

这种嵌套循环的方法通过比较数组中每一对可能的元素来工作。虽然它易于理解，但对于非常大的数组来说效率可能会变得很低。在接下来的步骤中，我们将探索更高效的查找重复元素的方法。

使用 HashSet 高效检查重复元素

在上一步中，我们使用嵌套循环来查找重复元素，这种方法简单但对于大型数组来说速度可能较慢。在这一步中，我们将学习一种更高效的方法，即使用 HashSet 来查找重复元素。

HashSet 是 Java 中的一种集合，用于存储唯一的元素。这意味着，如果你尝试向 HashSet 中添加一个已经存在的元素，添加操作将会失败（更准确地说，会返回 false）。我们可以利用这一特性来高效地检测重复元素。

基本思路如下：我们遍历数组，对于每个元素，尝试将其添加到一个 HashSet 中。如果 add() 方法返回 false，则说明该元素已经存在于集合中，因此它是一个重复元素。

让我们在你的 ~/project 目录下创建一个名为 FindDuplicatesHashSet.java 的新 Java 文件。

在代码编辑器中打开 FindDuplicatesHashSet.java 文件，并添加以下 Java 代码：

import java.util.HashSet;
import java.util.Set;

public class FindDuplicatesHashSet {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        // Create a HashSet to store unique elements
        Set<Integer> uniqueElements = new HashSet<>();

        System.out.println("Finding duplicate elements using HashSet:");

        // Iterate through the array
        for (int number : numbers) {
            // Try to add the element to the HashSet
            // If add() returns false, the element is a duplicate
            if (!uniqueElements.add(number)) {
                System.out.println("Duplicate found: " + number);
            }
        }
    }
}

让我们来看看这段代码的新部分：

• import java.util.HashSet; 和 import java.util.Set;：这两行代码导入了使用 HashSet 所需的类。
• Set<Integer> uniqueElements = new HashSet<>();：这行代码创建了一个空的 HashSet，用于存储 Integer 对象。我们使用 Set 作为类型，因为 HashSet 实现了 Set 接口。
• for (int number : numbers)：这是一个增强型 for 循环（也称为 for-each 循环），是遍历 numbers 数组中每个元素的便捷方式。
• !uniqueElements.add(number)：这是核心逻辑。uniqueElements.add(number) 尝试将当前的 number 添加到 HashSet 中。如果该数字已经存在，add() 方法将返回 false。! 运算符对这个结果取反，因此只有当 add() 返回 false 时，if 条件才为真，这表明找到了一个重复元素。

保存文件（Ctrl + S 或 Cmd + S）。

现在，在终端中编译 Java 代码：

javac FindDuplicatesHashSet.java

如果编译成功，运行程序：

java FindDuplicatesHashSet

你应该会看到输出列出了使用 HashSet 方法找到的重复元素。请注意，这种方法通常比嵌套循环方法更快，尤其是对于较大的数组，因为在 HashSet 中添加和检查元素的操作非常高效。

对排序后的数组进行测试

在这最后一步中，我们将探索另一种查找重复元素的方法，特别是当数组已经排序的情况。如果数组是有序的，重复元素总是相邻的。这使得通过比较相邻元素来查找重复元素变得非常简单和高效。

首先，在你的 ~/project 目录下创建一个名为 FindDuplicatesSorted.java 的新 Java 文件。

在代码编辑器中打开 FindDuplicatesSorted.java 文件，并添加以下 Java 代码：

import java.util.Arrays;

public class FindDuplicatesSorted {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 2, 7, 8, 8, 3};

        // First, sort the array
        Arrays.sort(numbers);

        System.out.println("Finding duplicate elements in a sorted array:");

        // Iterate through the sorted array and compare adjacent elements
        for (int i = 0; i < numbers.length - 1; i++) {
            // If the current element is equal to the next element, it's a duplicate
            if (numbers[i] == numbers[i + 1]) {
                System.out.println("Duplicate found: " + numbers[i]);
            }
        }
    }
}

让我们来分析这段代码的关键部分：

• import java.util.Arrays;：这行代码导入了 Arrays 类，该类提供了数组的实用方法，包括排序。
• Arrays.sort(numbers);：这行代码将 numbers 数组按升序排序。
• for (int i = 0; i < numbers.length - 1; i++)：这个循环遍历排序后的数组。我们循环到 numbers.length - 1，因为我们要将当前元素 (numbers[i]) 与下一个元素 (numbers[i + 1]) 进行比较。
• if (numbers[i] == numbers[i + 1])：这个条件检查当前元素是否等于下一个元素。如果它们相同，就意味着我们找到了一个重复元素。

保存文件（Ctrl + S 或 Cmd + S）。

现在，在终端中编译 Java 代码：

javac FindDuplicatesSorted.java

如果编译成功，运行程序：

java FindDuplicatesSorted

你应该会看到输出列出了找到的重复元素。注意，由于数组是有序的，重复元素在输出中会连续出现。

这种方法对于排序后的数组非常高效，因为在排序后只需要对数组进行一次遍历。然而，初始的排序步骤本身是有时间成本的，这取决于 Arrays.sort() 使用的排序算法。对于像 int 这样的基本类型，Java 的 Arrays.sort() 使用双轴快速排序，其平均时间复杂度为 O(n log n)。

你现在已经探索了三种在 Java 数组中查找重复元素的不同方法：使用嵌套循环、使用 HashSet 和使用排序后的数组。每种方法在简单性、效率和要求（如数组是否有序）方面都有各自的权衡。理解这些不同的方法对于为特定问题选择最合适的方法非常有价值。

总结

在这个实验中，我们探索了在 Java 中检查数组是否包含重复元素的不同方法。首先，我们实现了一种使用嵌套循环的简单方法，该方法需要将数组中的每个元素与其他所有元素进行比较。这种方法虽然易于理解，但其时间复杂度为 O(n^2)，对于大型数组来说效率较低。

接下来，我们学习了如何利用 HashSet 数据结构进行更高效的重复元素检查。通过遍历数组并尝试将每个元素添加到 HashSet 中，我们可以快速判断一个元素是否为重复元素，因为如果元素已经存在，HashSet 的 add() 方法会返回 false。这种方法的时间复杂度有显著提升，平均情况下通常为 O(n)。最后，我们探讨了先对数组进行排序也能高效地查找重复元素，因为排序后重复元素会相邻。