Java如何打印数组元素间的缺失值？现有HashSet代码输出异常求优化

先说说你这段HashSet代码的问题：

• 第二个循环的范围完全错了：你循环的是i从1到set.size()-1（也就是1到4），但你的数组数值范围是2到11，根本没覆盖到后面的数；
• 输出的是set.size()而不是当前的i，所以每次都打印5，自然看不到正确的缺失值。

不过你问的是除了HashSet之外的可行方法，下面给你两种实用的方案：

方法一：利用数组有序性遍历相邻元素 #

你的数组是升序排列的，直接遍历数组中相邻的两个元素，计算它们的差值，如果差值大于1，就把中间的所有数输出出来。代码示例：

public class test {
    public static void main(String[] args) {
        int[] array = {2,4,6,8,11};
        for (int i = 0; i < array.length - 1; i++) {
            int current = array[i];
            int next = array[i+1];
            // 如果两个数之间有间隔
            if (next - current > 1) {
                // 遍历中间的所有数
                for (int j = current + 1; j < next; j++) {
                    System.out.print(j + " ");
                }
            }
        }
    }
}

这个方法的优势是不需要额外的集合或数组，空间复杂度O(1)，效率很高，前提是数组已经是有序的。

方法二：使用布尔数组标记存在的数值 #

先找到数组的最小值和最大值，创建一个布尔数组来标记哪些数是存在的，最后遍历布尔数组找出未标记的数。代码示例：

public class test {
    public static void main(String[] args) {
        int[] array = {2,4,6,8,11};
        // 先找数组的最小和最大值
        int min = array[0];
        int max = array[0];
        for (int num : array) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        // 创建布尔数组，标记存在的数
        boolean[] exists = new boolean[max - min + 1];
        for (int num : array) {
            exists[num - min] = true;
        }
        // 遍历布尔数组，输出缺失的数
        for (int i = 0; i < exists.length; i++) {
            if (!exists[i]) {
                System.out.print((min + i) + " ");
            }
        }
    }
}

这个方法不管数组是否有序都能工作，空间复杂度取决于最大值和最小值的差，适合数值范围不大的场景。

内容的提问来源于stack exchange，提问作者Mai Sakurajima