Java中查找数组中缺失的数字

本文将介绍如何在Java中高效地查找一个已排序整数数组中缺失的数字。通过一个简单的嵌套循环方法，我们能够遍历数组并识别出所有不连续的数字，从而确定缺失的数字。本文将提供代码示例，并解释其工作原理，帮助你理解和应用这种方法。

查找缺失数字的算法

给定一个升序排列的整数数组，我们的目标是找出数组中缺失的数字。例如，对于数组 [12, 13, 17, 18, 20, 21, 24, 25, 26]，缺失的数字是 14, 15, 16, 19, 22, 23。

一种简单而有效的方法是使用嵌套循环。外层循环遍历数组，内层循环检查当前元素和下一个元素之间的所有数字。

代码示例

以下是使用嵌套循环在Java中查找缺失数字的示例代码：

立即学习“Java免费学习笔记（深入）”；

public class MissingNumber {
    public static void main(String[] args) {
        int[] arr = {12, 13, 17, 18, 20, 21, 24, 25, 26};

        System.out.println("Missing numbers:");
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = arr[i] + 1; j < arr[i + 1]; j++) {
                System.out.println(j);
            }
        }
    }
}

代码解释：

1. 外层循环： for (int i = 0; i < arr.length - 1; i++) 遍历数组 arr，从第一个元素到倒数第二个元素。我们只需要遍历到倒数第二个元素，因为内层循环会比较当前元素和下一个元素。

   

   怪兽AI数字人

   数字人短视频创作，数字人直播，实时驱动数字人

   44

   查看详情

2. 内层循环： for (int j = arr[i] + 1; j < arr[i + 1]; j++) 遍历从 arr[i] + 1 到 arr[i + 1] - 1 的所有数字。这个循环检查当前元素 arr[i] 和下一个元素 arr[i + 1] 之间的所有数字。

3. 输出缺失数字： System.out.println(j); 打印内层循环中遍历的每个数字 j。这些数字就是数组中缺失的数字。

输出结果：

Missing numbers:
14
15
16
19
22
23

示例分析

• 当 i = 0 时，arr[0] = 12，arr[1] = 13。内层循环从 13 开始，到 13 结束（不包含 13），因此没有输出。
• 当 i = 1 时，arr[1] = 13，arr[2] = 17。内层循环从 14 开始，到 16 结束，因此输出 14、15 和 16。
• 当 i = 2 时，arr[2] = 17，arr[3] = 18。内层循环从 18 开始，到 18 结束（不包含 18），因此没有输出。
• 以此类推，直到遍历完整个数组。

性能分析

该算法的时间复杂度为 O(n*m)，其中 n 是数组的长度，m 是数组中相邻元素之间的最大差值。在最坏情况下，如果数组中所有相邻元素之间的差值都很大，那么算法的性能会下降。但是，在大多数情况下，该算法的性能是可以接受的。

总结

使用嵌套循环是在Java中查找排序数组中缺失数字的一种简单而有效的方法。该算法易于理解和实现，并且在大多数情况下性能良好。希望本教程能够帮助你理解和应用这种方法。

以上就是Java中查找数组中缺失的数字的详细内容，更多请关注php中文网其它相关文章！