字符串排列实现无法适配整数数组的技术问题咨询

嘿，你的字符串排列逻辑很扎实啊！要适配整数数组的话，咱们可以基于这个递归核心思路做两种改造，我给你详细说说：

方案一：直接修改代码支持整数数组（推荐） #

原代码的递归逻辑是通用的——每次从剩余元素里选一个加入已构建的结果，直到剩余元素为空就存入列表。咱们把字符串相关的操作换成整数数组/列表的操作就行，核心逻辑不变：

import java.util.ArrayList;
import java.util.List;

public class PermutationUtils {
    // 对外暴露的整数数组排列方法
    public static List<List<Integer>> myperm(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        mypermImpl(new ArrayList<>(), nums, result);
        return result;
    }

    // 递归实现方法
    private static void mypermImpl(List<Integer> built, int[] remaining, List<List<Integer>> result) {
        if (remaining.length == 0) {
            // 注意这里要新建列表，避免后续回溯修改已存入的结果
            result.add(new ArrayList<>(built));
            return;
        }

        for (int i = 0; i < remaining.length; i++) {
            // 把当前选中的整数加入已构建列表
            built.add(remaining[i]);
            // 生成排除当前元素的剩余数组
            int[] newRemaining = new int[remaining.length - 1];
            System.arraycopy(remaining, 0, newRemaining, 0, i);
            System.arraycopy(remaining, i + 1, newRemaining, i, remaining.length - i - 1);
            // 递归调用
            mypermImpl(built, newRemaining, result);
            // 回溯：移除刚添加的元素，保证下一次循环状态正确
            built.remove(built.size() - 1);
        }
    }

    // 测试用例
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> permutations = myperm(nums);
        for (List<Integer> perm : permutations) {
            System.out.println(perm);
        }
    }
}

关键改动说明： #

• 把原有的String类型的built和other换成了List<Integer>和int[]，更贴合整数数组场景
• 用System.arraycopy替代字符串的substring操作，生成排除当前元素的剩余数组
• 递归结束时要新建ArrayList存入结果，因为built是会被回溯修改的引用
• 增加回溯步骤：递归返回后移除刚添加的元素——原字符串是不可变类型，拼接后不会影响原有值，所以不需要这一步，但整数列表是可变的，必须回溯才能保证循环状态正确

方案二：转字符串复用原代码（简单但有局限） #

如果想偷懒尽量复用原代码，也可以先把整数数组转成字符串，用原方法生成排列后再转回整数列表，但这种方式有明显局限性：

import java.util.ArrayList;
import java.util.List;

public class StringToIntPerm {
    // 原有的字符串排列方法
    public static List<String> myperm(String s) {
        List<String> l = new ArrayList<>();
        mypermImpl("", s, l);
        return l;
    }

    private static void mypermImpl(String built, String other, List<String> l) {
        if (other.length() == 0) {
            l.add(built);
        }
        for (int i = 0; i < other.length(); i++) {
            String leftover = other.substring(0, i) + other.substring(i + 1);
            mypermImpl(built + other.charAt(i), leftover, l);
        }
    }

    // 适配整数数组的包装方法
    public static List<List<Integer>> mypermForIntArray(int[] nums) {
        // 把整数数组转成字符串，比如[1,2,3]转成"123"
        StringBuilder sb = new StringBuilder();
        for (int num : nums) {
            sb.append(num);
        }
        List<String> strPerms = myperm(sb.toString());
        
        // 把排列后的字符串转回整数列表
        List<List<Integer>> result = new ArrayList<>();
        for (String str : strPerms) {
            List<Integer> intList = new ArrayList<>();
            for (char c : str.toCharArray()) {
                intList.add(c - '0');
            }
            result.add(intList);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> permutations = mypermForIntArray(nums);
        for (List<Integer> perm : permutations) {
            System.out.println(perm);
        }
    }
}

注意事项： #

• 这种方式只适合单个数字的整数（0-9），如果数组中有多位数（比如12、345），转字符串后会被拆分成单个数字，导致结果完全错误
• 性能和可读性都不如方案一，只适合临时快速改造

推荐优先用方案一，它更贴合整数数组的使用场景，也避免了字符串转换带来的限制和额外开销。

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