59
#yyds干货盘点# 面试必刷TOP101：没有重复项数字的全排列
source link: https://blog.51cto.com/u_15488507/5689133
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 面试必刷TOP101：没有重复项数字的全排列
精选 原创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]]
[[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;
}
}
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;
}
}
- 赞
- 收藏
- 评论
- 分享
- 举报
</div
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK