美文网首页
全排列算法

全排列算法

作者: PENG先森_晓宇 | 来源:发表于2023-03-12 22:31 被阅读0次

    给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

    示例 1:

    输入:nums = [1,2,3]
    输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    

    算法如下:

    class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> ret = new ArrayList<>();
            List<Integer> target = new ArrayList<>();
            for (int num:nums){
                target.add(num);
            }
            trance(ret,0,nums.length,target);
            return ret;
        }
        public void trance(List<List<Integer>> ret,int cursor,int length,List<Integer> target){
            if(cursor == length-1){
                //这里要注意:要重新实例化一个ArrayList,因为target是一个引用地址
                ret.add(new ArrayList<Integer>(target));
                return;
            }
            //这里的思想很重要,以cursor下标为点,依次和cursor后面的下标交换,这样就会得出cursor下标不同值的n个数组,
            //cursor下标排完之后,在以cursor+1下标为准,一次进行上述操作,当cursor为length-1时则全部遍历完了,依次
            //添加进数组即可。
            for (int i = cursor;i<length;i++){
                Collections.swap(target,cursor,i);
                trance(ret,cursor+1,length,target);
                Collections.swap(target,cursor,i);
            }
        }
    }
    

    这个算法有俩个疑问点:

    • 为什么cursor == length-1时才需要添加add呢?看下图的递归树就明白了
    • 为什么 Collections.swap(target,cursor,i)之后还需要 Collections.swap(target,cursor,i)呢?
      举个例子,原数组1,2,3 当游标为0时的意思是后面的元素2和3都和1元素置换。
      当第一次置换之后为2 ,1,3,此时我们需要将2,1,3还原成1,2,3之后才能继续和3置换成3,2,1,如果不还原成1,2,3直接置换之后的结果为3,1,2了

    相关文章

      网友评论

          本文标题:全排列算法

          本文链接:https://www.haomeiwen.com/subject/eyvqrdtx.html