全排列算法

2023-03-12  本文已影响0人  PENG先森_晓宇

给定一个不含重复数字的数组 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);
        }
    }
}

这个算法有俩个疑问点:

上一篇下一篇

猜你喜欢

热点阅读