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

1.简述:

描述

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

例如:

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

数据范围:数字个数 #yyds干货盘点# 面试必刷TOP101:没有重复项数字的全排列

要求:空间复杂度 #yyds干货盘点# 面试必刷TOP101:没有重复项数字的全排列 ,时间复杂度 #yyds干货盘点# 面试必刷TOP101:没有重复项数字的全排列

示例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;
}
}
发表评论

相关文章