Java中判断两数组是否为置换：递归方法的挑战与高效排序解决方案

public class RecursionExample {

    /**
     * 计算斐波那契数列的第n个数字。
     * 这是一个典型的递归函数示例，清晰地展示了基本情况和递归步骤。
     *
     * @param n 斐波那契数列的索引
     * @return 第n个斐波那契数
     */
    public static int fib(int n) {
        // 基本情况：n为0或1时，直接返回n
        if (n == 0 || n == 1) {
            return n;
        }
        // 递归步骤：将问题分解为更小的子问题
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        System.out.println("fib(0) = " + fib(0)); // 输出: 0
        System.out.println("fib(1) = " + fib(1)); // 输出: 1
        System.out.println("fib(5) = " + fib(5)); // 输出: 5 (0, 1, 1, 2, 3, 5)
    }
}

// 这是一个有缺陷的递归尝试，无法正确判断置换
public static boolean isPermutationFlawed(int[] a, int[] b, int indexA, int indexB) {
    // 长度不等或索引越界，直接返回false
    if (a.length != b.length || indexA >= a.length || indexB >= b.length) {
        return false;
    }
    // 问题所在：如果找到一个匹配，就立即返回true，而没有检查其他元素
    if (a[indexA] == b[indexB]) {
        return true; // 此处逻辑错误，不能提前返回
    }
    // 如果当前元素不匹配，则尝试下一个组合
    // 这种尝试也无法保证所有元素都被检查且一一对应
    return isPermutationFlawed(a, b, indexA + 1, 0) || isPermutationFlawed(a, b, indexA, indexB + 1);
}

import java.util.Arrays;

public class PermutationCheck {

    /**
     * 判断两个整数数组是否为彼此的置换。
     * 该方法通过排序数组然后进行比较来实现，效率高且逻辑清晰。
     *
     * @param a 第一个整数数组
     * @param b 第二个整数数组
     * @return 如果两个数组是彼此的置换，则返回true；否则返回false。
     */
    public static boolean arePermutations(int[] a, int[] b) {
        // 1. 长度检查：如果长度不同，它们不可能互为置换
        if (a.length != b.length) {
            return false;
        }

        // 2. 克隆数组：避免修改原始数组（如果需要）
        int[] sortedA = Arrays.copyOf(a, a.length);
        int[] sortedB = Arrays.copyOf(b, b.length);

        // 3. 排序：对两个数组进行排序
        Arrays.sort(sortedA);
        Arrays.sort(sortedB);

        // 4. 比较：排序后，如果两个数组相等，则它们是彼此的置换
        return Arrays.equals(sortedA, sortedB);
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3, 4};
        int[] arr2 = {4, 3, 2, 1};
        int[] arr3 = {1, 2, 3, 5};
        int[] arr4 = {1, 1, 2, 3};
        int[] arr5 = {1, 2, 3, 3};

        System.out.println("arr1 和 arr2 是置换吗？ " + arePermutations(arr1, arr2)); // true
        System.out.println("arr1 和 arr3 是置换吗？ " + arePermutations(arr1, arr3)); // false
        System.out.println("arr1 和 arr4 是置换吗？ " + arePermutations(arr1, arr4)); // false
        System.out.println("arr4 和 arr5 是置换吗？ " + arePermutations(arr4, arr5)); // true
        System.out.println("空数组和空数组是置换吗？ " + arePermutations(new int[]{}, new int[]{})); // true
        System.out.println("空数组和非空数组是置换吗？ " + arePermutations(new int[]{}, new int[]{1})); // false
    }
}