网站建设公司电话,萨隆wordpress,邵东做网站,网站修改需要什么描述
给出一组数字#xff0c;返回该组数字的所有排列
例如#xff1a;
[1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. #xff08;以数字在数组中的位置靠前为优先级#xff0c;按字典序排列输出。#xff09;
数据范围#xff1a;数字…描述
给出一组数字返回该组数字的所有排列
例如
[1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. 以数字在数组中的位置靠前为优先级按字典序排列输出。
数据范围数字个数 0n≤6
要求空间复杂度 O(n!)时间复杂度 O(n!
示例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]]
思路分析
经典的回溯算法问题——全排列Permutations permute 方法这是类的公共方法接收一个整数数组 num 作为输入并返回一个 ArrayListArrayListInteger 类型的列表其中每个内部列表代表 num 数组的一个排列。 初始化一个 ArrayListArrayListInteger 类型的 result 列表用于存储所有排列。初始化一个 LinkedListInteger 类型的 list用于在回溯过程中构建当前的排列。调用 backTrack 方法开始回溯过程。 backTrack 方法这是一个私有方法用于递归地生成所有排列。它接收三个参数 num原始整数数组。 list当前正在构建的排列以链表形式。 result用于存储所有排列的列表。 递归终止条件如果 list 的大小等于 num 的长度说明已经构建了一个完整的排列此时将这个排列通过 new ArrayListInteger(list) 转换为不可变列表添加到 result 中并返回。 递归过程遍历 num 数组中的每个元素如果当前元素已经存在于 list 中则跳过该元素避免重复排列。否则将该元素添加到 list 中并递归调用 backTrack 方法继续构建下一个元素。递归返回后需要撤销上一步的选择即移除 list 中最后添加的元素以便尝试其他可能的排列。
代码
import java.util.*;public class Solution {public ArrayListArrayListInteger permute(int[] num) {ArrayListArrayListInteger result new ArrayList();LinkedListInteger list new LinkedList();backTrack(num, list, result);return result;}private void backTrack(int[] num, LinkedListInteger list,ArrayListArrayListInteger result) {if (list.size() num.length) {result.add(new ArrayListInteger(list));return;}for (int i 0; i num.length; i) {if (list.contains(num[i])) {continue;}list.add(num[i]);backTrack(num, list, result);list.removeLast();}}
}
