#yyds干货盘点# 面试必刷TOP101：没有重复项数字的全排列

来源：恒创科技编辑：恒创科技编辑部

2024-01-28 10:05:59

1.简述：

描述

给出一组数字，返回该组数字的所有排列

例如：

[1,2,3]的所有排列如下[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数

要求：空间复杂度，时间复杂度

示例1

输入：

[1,2,3]

返回值：

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2

输入：

[1]

返回值：

[[1]]

2.代码实现：

import java.util.*;
public class Solution {
    //交换位置函数
    private void swap(ArrayList<Integer> num, int i1, int i2{ 
        int temp = num.get(i1);
        num.set(i1, num.get(i2));
        num.set(i2, temp);
    }
    
    public void recursion(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> num, int index){
        //分枝进入结尾，找到一种排列
        if(index == num.size() - 1){
            res.add(num);
        }
        else{
            //遍历后续的元素
            for(int i = index; i < num.size(); i++){ 
                //交换二者
                swap(num, i, index); 
                //继续往后找
                recursion(res, num, index + 1); 
                //回溯
                swap(num, i, index); 
            }
        }
    }
    
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        //先按字典序排序
        Arrays.sort(num);  
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> nums = new ArrayList<Integer>();
        //数组转ArrayList
        for(int i = 0; i < num.length; i++) 
            nums.add(num[i]);
        recursion(res, nums, 0);
        return res;
    }
}