Java对比两个int数组查找缺失数字问题求助

嘿，刚看了你的问题，作为Java新手能想到用boolean数组来标记存在的数字，这个思路其实是对的！咱们一步步来搞定这个问题：

为什么会出现ArrayIndexOutOfBoundsException？ #

你修改后的代码里出现越界错误，核心原因是数组索引和数字范围不匹配：

• 你输入的n是标准序列的最大值（比如n=9，序列是1~9），但你创建的boolean[] id长度是n，数组索引范围是0~n-1（也就是0~8）。
• 当你输入的数字是n（比如9）时，执行id[head[i]] = true就会尝试访问id[9]，但数组最大索引是8，自然就越界了。

修正方案（两种思路，选你顺手的） #

思路1：让boolean数组覆盖1~n的索引 #

把boolean数组的长度设为n+1，这样索引可以从0到n，我们只使用1~n的部分，刚好对应标准序列的数字：

import java.util.Scanner;

public class findLeaves {
    private boolean[] id;
    private int[] head;

    public boolean[] inputId() {
        System.out.println("Input number of IDs");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        // 数组长度设为n+1，覆盖1~n的索引
        id = new boolean[n + 1];
        return this.id;
    }

    public int[] inputHead() {
        System.out.println("Input each head value.");
        // 只用一个Scanner就够啦，不用循环里重复创建
        Scanner scan = new Scanner(System.in);
        // 这里假设用户输入n个以内的1~n数字（允许缺失）
        // 如果想让用户自由输入个数，可以改成动态列表，新手先简化用固定长度
        head = new int[id.length - 1];
        for (int i = 0; i < head.length; i++) {
            head[i] = scan.nextInt();
        }
        return this.head;
    }

    public boolean Leaves() {
        // 标记所有存在的数字
        for (int num : head) {
            // num是1~n，id数组长度是n+1，索引num合法
            id[num] = true;
        }
        // 遍历1~n，找出未标记的缺失数字
        System.out.println("缺失的数字是：");
        for (int j = 1; j < id.length; j++) {
            if (!id[j]) {
                System.out.print(j + " ");
            }
        }
        return true;
    }

    public static void main(String[] args) {
        findLeaves x = new findLeaves();
        x.inputId();
        x.inputHead();
        x.Leaves();
    }
}

思路2：将输入的数字减1，对应0~n-1的索引 #

如果不想改变数组长度，就把输入的数字减1，映射到0~n-1的索引，最后输出的时候再加1还原：

import java.util.Scanner;

public class findLeaves {
    private boolean[] id;
    private int[] head;

    public boolean[] inputId() {
        System.out.println("Input number of IDs");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        id = new boolean[n];
        return this.id;
    }

    public int[] inputHead() {
        System.out.println("Input each head value.");
        Scanner scan = new Scanner(System.in);
        head = new int[id.length];
        for (int i = 0; i < head.length; i++) {
            int num = scan.nextInt();
            // 把数字减1，对应数组的0~n-1索引
            head[i] = num - 1;
        }
        return this.head;
    }

    public boolean Leaves() {
        for (int index : head) {
            // index是合法的0~n-1索引，不会越界
            id[index] = true;
        }
        System.out.println("缺失的数字是：");
        for (int j = 0; j < id.length; j++) {
            if (!id[j]) {
                // 输出时加1，还原成原来的1~n数字
                System.out.print((j + 1) + " ");
            }
        }
        return true;
    }

    public static void main(String[] args) {
        findLeaves x = new findLeaves();
        x.inputId();
        x.inputHead();
        x.Leaves();
    }
}

额外的小建议 #

• 不要在循环里重复创建Scanner对象，一个就够了，多次创建可能会导致输入异常。
• 可以加个输入验证，比如判断用户输入的数字是否在1~n范围内，避免非法输入导致的错误（比如输入0或者大于n的数）。

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