网站备案接入商名称,宝安西乡做网站,济宁网站建设有限公司,中国建设银行蚌埠官方网站基础知识要求#xff1a; Java#xff1a;方法、集合、泛型、Arrays工具类、数组、for循环、if判断 Python#xff1a; 方法、列表、for循环、if判断 题目#xff1a;
给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案…基础知识要求 Java方法、集合、泛型、Arrays工具类、数组、for循环、if判断 Python 方法、列表、for循环、if判断 题目
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2
输入nums [0,1]
输出[[0,1],[1,0]]示例 3
输入nums [1]
输出[[1]]提示
1 nums.length 6-10 nums[i] 10nums 中的所有整数 互不相同
思路解析
为了生成一个数组的所有可能全排列我们可以使用回溯法backtracking。回溯法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解或者至少不是最后一个解回溯算法会通过在上一步进行一些更改来丢弃该解即“回溯”并尝试其他可能的解。
Java代码示例
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List; public class Permutations { public ListListInteger permute(int[] nums) { ListListInteger result new ArrayList(); int n nums.length; boolean[] used new boolean[n]; ListInteger tempList new ArrayList(); backtrack(nums, used, tempList, result, 0); return result; } private void backtrack(int[] nums, boolean[] used, ListInteger tempList, ListListInteger result, int first) { if (first nums.length) { result.add(new ArrayList(tempList)); // 添加当前排列到结果中 } for (int i 0; i nums.length; i) { if (!used[i]) { // 如果当前数字没有被使用过 used[i] true; // 标记为已使用 tempList.add(nums[i]); // 将当前数字添加到当前排列中 backtrack(nums, used, tempList, result, first 1); // 递归进行下一个数字的排列 tempList.remove(tempList.size() - 1); // 回溯撤销当前选择 used[i] false; // 回溯撤销使用标记 } } } public static void main(String[] args) { Permutations permutations new Permutations(); int[] nums {1, 2, 3}; ListListInteger result permutations.permute(nums); for (ListInteger permutation : result) { System.out.println(permutation); } }
} Python代码示例
def permute(nums): def backtrack(first 0): # 如果所有整数都填完了 if first n: output.append(nums[:]) for i in range(first, n): # 动态地维护数组 nums[first], nums[i] nums[i], nums[first] # 继续递归填下一个数 backtrack(first 1) # 撤销操作 nums[first], nums[i] nums[i], nums[first] n len(nums) output [] backtrack() return output # 示例
nums [1,2,3]
print(permute(nums))
