描述
给定一个数字列表,返回其所有可能的排列。
你可以假设没有重复数字。
【给定一个数字列表,返回其所有可能的排列,打败了70%,比参考答案运行还快】您在真实的面试中是否遇到过这个题?
样例
样例 1:
输入:[1]
输出:
[
[1]
]
样例 2:
输入:[1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
自己写了一套算法,打败了70%,还可以继续优化,比参考答案运行还快!!!
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
public static List> permute(int[] nums) {
// write your code here
List> lists=new ArrayList<>();
if (nums==null || nums.length==0){
List list=new ArrayList<>();
lists.add(list);
return lists;
}
if (nums.length==1){
List list=new ArrayList<>();
list.add(nums[0]);
lists.add(list);
return lists;
}
test(nums,lists,0);
return lists;
}public static void test(int[]nums,List> list,int index){
List list1=new ArrayList<>();
List list2=new ArrayList<>();
if ((index+2)==nums.length){
for (int i = 0;
i < index;
i++) {
list1.add(nums[i]);
list2.add(nums[i]);
}
list1.add(nums[index]);
list1.add(nums[nums.length-1]);
list2.add(nums[nums.length-1]);
list2.add(nums[index]);
list.add(list1);
list.add(list2);
}else {
for (int i=0;
i<(nums.length-index);
i++){
if (i!=0){
//交换数组位置
int temp=nums[index];
nums[index]=nums[index+i];
nums[index+i]=temp;
int a=index+1;
test(nums,list,a);
//交换到原来得位置
int temp1=nums[index+i];
nums[index+i]=nums[index];
nums[index]=temp1;
}else {
int a=index+1;
test(nums,list,a);
}
}
}
}
推荐阅读
- 人工智能|干货!人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题(持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点(详细介绍 Python 中的 7 种交叉验证方法!)
- 网络|简单聊聊压缩网络