请问这四种方式都是全排列吗,排列输出的顺序也不一样,它们的思路都是怎样的呢,有什么区别吗?

1、第一种


import java.util.Arrays;


public class Main {


    

    public static void main(String[] args) {

        int[] a = new int[] { 1, 2, 3, 4 };

        f(a, 0, a.length - 1);

    }


    public static void f(int[] a, int start, int end) {


        if (start >= end) {

            System.out.println(Arrays.toString(a));

            return;

        }


        for (int i = start; i <= end; i++) {

            int temp = a[start];

            a[start] = a[i];

            a[i] = temp;

            f(a, start + 1, end);

            temp = a[start];

            a[start] = a[i];

            a[i] = temp;

        }

    }

}

第二种


import java.util.Arrays;


public class Main {


    public static void main(String[] args) {

        int[] a = new int[4];

        boolean[] vis = new boolean[5];

        f(a, 0, vis);

    }


    public static void f(int[] a, int k, boolean[] vis) {


        if (k >= a.length) {

            System.out.println(Arrays.toString(a));

        }


        for (int i = 1; i <= a.length; i++) {

            if (!vis[i]) {

                a[k] = i;

                vis[i] = true;

                f(a, k + 1, vis);

                vis[i] = false;

            }

        }

    }

}

第三种


import java.util.Arrays;


public class Main {


    public static void main(String[] args) {

        int[] a = new int[4];

        boolean[] vis = new boolean[4];

        f(a, 1, vis);

    }


    public static void f(int[] a, int k, boolean[] vis) {


        if (k > a.length) {

            System.out.println(Arrays.toString(a));

            return;

        }


        for (int i = 0; i < a.length; i++) {

            if (!vis[i]) {

                a[i] = k;

                vis[i] = true;

                f(a, k + 1, vis);

                vis[i] = false;

            }


        }

    }

}



慕标琳琳
浏览 380回答 1
1回答

交互式爱情

除第一种是对数组的元素进行全排列, 其余的都是对数组边赋值边进行排列的, 所以后面三种其实说是对"数组进行全排列"这种说法并不对, 只不过是下标刚好是和数值一样了对全排列的基本思想都是一样的, 使用递归前保存原来的状态, 递归弹出后恢复.结果不一样是因为对a[i]的赋值不同, 第二种是a[i] = i, 三四种a[i] = k;第四种的相当于二三种的简化,vis的标记位与a数组合并了, 但是这样不能对{0, 1, 2}这种数组进行全排列了, 因为0相当于未访问意思了第一种的end完全可以不用传, 本质就是数组长度
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

Java