Java数组找缺失数字技巧分享

大家好，今天本人给大家带来文章《Java数组找缺失数字方法详解》，文中内容主要涉及到，如果你对文章方面的知识点感兴趣，那就请各位朋友继续看下去吧~希望能真正帮到你们，谢谢！

本教程详细介绍了在Java中如何查找给定范围内（从1到指定最大值）未出现在无序整数数组中的数字。文章分析了常见的错误，并提供了两种主要的解决方案：一种是利用`HashSet`进行高效查找，适用于大型数组；另一种是实现自定义的线性查找方法，适用于小型数组，并简要提及了排序加二分查找的策略，旨在帮助开发者选择最适合其场景的方法。

识别数组中缺失的数字

在编程实践中，我们经常会遇到需要在一个指定范围内，找出哪些数字没有出现在一个给定的无序数组中的场景。例如，给定一个最大值max和一个整数数组A，我们的目标是打印出所有从1到max之间，但不在数组A中的数字。

常见误区分析

初学者在尝试解决此类问题时，可能会倾向于创建一个有序的参考数组，然后将输入数组中的元素与参考数组进行比较。然而，如果比较逻辑不当，可能会导致打印出数组中“已包含”的数字，而非“未包含”的数字。

以下是一个典型的错误示例，它错误地打印了数组A中已存在的数字：

public class Test {

    public static void main(String[] args) {
        int max = 5;
        int[] A = {1, 2, 3, 5};

        // 创建一个有序的参考数组B
        int[] B = new int[max];
        int num = 1;
        for (int i = 0; i < max; i++) {
            B[i] = num;
            num++;
        }

        // 错误的检查逻辑：这将打印A中已包含的数字
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                if (A[i] == B[j]) {
                    System.out.println(B[j]); // 打印的是A中存在的数字
                }
            }
        }
    }
}

上述代码的本意是找出缺失的数字，但由于if (A[i] == B[j])条件成立时打印B[j]，它实际上输出了数组A中已有的元素（1, 2, 3, 5），这与我们的目标相反。要找到缺失的数字，我们需要的是在外部循环中遍历完整的范围，并在内部判断当前数字是否不在数组A中。

解决方案

为了正确地找出并打印缺失的数字，我们可以采用以下几种策略。

方案一：使用 HashSet 进行高效查找

当处理大型数组时，将输入数组转换为 HashSet 是一个非常高效的方法。HashSet 提供了平均 O(1) 时间复杂度的 contains() 方法，这使得查找操作极其迅速。

实现步骤：

1. 将输入的整数数组转换为 HashSet。这将允许我们快速检查某个数字是否存在于原始数组中。
2. 从1遍历到 max。
3. 对于范围内的每个数字，使用 HashSet 的 contains() 方法检查它是否在集合中。
4. 如果 contains() 返回 false，则表示该数字是缺失的，将其打印出来。

示例代码：

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

public class MissingNumberFinder {

    public static void main(String[] args) {
        int max = 5;
        // 注意：对于Set，需要使用包装类Integer
        Integer[] A = {1, 2, 3, 5}; 

        // 将数组A的元素添加到HashSet中
        Set<Integer> presentNumbers = new HashSet<>();
        Collections.addAll(presentNumbers, A);

        System.out.println("缺失的数字 (使用 HashSet):");
        // 遍历从1到max的每个数字
        for (int i = 1; i <= max; i++) {
            // 如果当前数字不在presentNumbers集合中，则它是缺失的
            if (!presentNumbers.contains(i)) {
                System.out.println(i);
            }
        }
    }
}

优点：

• 效率高： 对于大型数组，构建 HashSet 的时间复杂度是 O(N) (N为数组长度)，而后续的 contains() 操作平均时间复杂度是 O(1)。因此，整个查找过程的平均时间复杂度是 O(N + max)。
• 代码简洁： 利用Java集合框架的强大功能，代码可读性好。

注意事项：

• HashSet 存储的是对象，所以当从原始类型数组（如int[]）转换为集合时，需要使用包装类（如Integer[]）。

方案二：自定义线性查找方法

如果数组规模较小，或者希望避免创建额外的 Set 对象开销，可以实现一个自定义的线性查找函数。这种方法在每次检查时都需要遍历整个原始数组。

实现步骤：

1. 创建一个辅助函数 contains(Integer[] arr, int x)，它遍历数组 arr，如果找到 x 则返回 true，否则返回 false。
2. 从1遍历到 max。
3. 对于范围内的每个数字，调用自定义的 contains() 方法检查它是否在原始数组中。
4. 如果 contains() 返回 false，则打印该数字。

示例代码：

public class MissingNumberFinderCustom {

    // 自定义查找函数，检查数组arr中是否包含数字x
    public static boolean contains(Integer[] arr, int x) {
        for (int j = 0; j < arr.length; j++) {
            if (arr[j] == x) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int max = 5;
        Integer[] A = {1, 2, 3, 5};

        System.out.println("缺失的数字 (使用自定义查找):");
        // 遍历从1到max的每个数字
        for (int i = 1; i <= max; i++) {
            // 如果当前数字不在数组A中，则它是缺失的
            if (!contains(A, i)) {
                System.out.println(i);
            }
        }
    }
}

优点：

• 内存开销小： 不需要创建额外的 HashSet 对象。
• 简单直观： 对于理解查找逻辑而言，直接遍历数组更易于理解。

缺点：

• 效率较低： contains() 方法的每次调用都需要 O(N) 的时间复杂度（N为数组长度）。因此，整个查找过程的时间复杂度是 O(max * N)。对于大型数组和较大的 max 值，性能会显著下降。

方案三：排序与二分查找（进阶）

另一种优化方法是先对原始数组进行排序，然后利用二分查找。如果输入数组本身已经是有序的，或者排序的开销可以接受，这种方法会非常高效。

实现步骤：

1. 对数组 A 进行排序。
2. 从1遍历到 max。
3. 对于范围内的每个数字，使用 Arrays.binarySearch() 方法在已排序的数组 A 中进行查找。
4. 如果 binarySearch() 返回的值小于0，则表示该数字不存在于数组中，将其打印出来。

示例代码（概念性，不提供完整代码）：

import java.util.Arrays;

// ...
// 对数组A进行排序
// Arrays.sort(A); 
// for (int i = 1; i <= max; i++) {
//     if (Arrays.binarySearch(A, i) < 0) { // 如果查找结果小于0，表示未找到
//         System.out.println(i);
//     }
// }
// ...

优点：

• 效率高： 排序的时间复杂度通常为 O(N log N)，二分查找的时间复杂度为 O(log N)。因此，总时间复杂度为 O(N log N + max log N)。对于大型数组，这比线性查找高效。
• 适用于已排序数组： 如果输入数组经常是或可以假定为已排序，此方法非常理想。

缺点：

• 修改原始数组： Arrays.sort() 会修改原始数组的顺序。
• 排序开销： 如果数组非常大且无序，排序本身会带来一定的开销。

总结与选择建议

根据上述分析，我们可以得出以下结论和选择建议：

• 对于大多数场景和大型数组，推荐使用 HashSet 方案。 它在平均情况下提供了最佳的性能（O(N + max)），并且代码简洁易懂。
• 对于小型数组，或者对内存使用有严格限制，且性能要求不极致的场景，可以考虑自定义线性查找方法。 它的实现最简单，但时间复杂度较高（O(max * N)）。
• 如果数组经常是有序的，或者排序的开销可以接受，并且希望获得较高的性能，可以考虑排序加二分查找方案。

使用上述任何一种正确的方法，对于输入 max = 5 和 A = {1, 2, 3, 5}，预期的输出都将是：

4

在实际开发中，根据具体的数据规模、性能要求以及对内存的限制，选择最合适的方案至关重要。

好了，本文到此结束，带大家了解了《Java数组找缺失数字技巧分享》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！