凯发k8官方网
收集整理的这篇文章主要介绍了
[leetcode] permutations 全排列
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
given a collection of numbers, return all possible permutations.
for example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
交换法
复杂度
时间 o(n^2) 空间 o(n) 递归栈
思路
置换实际上是给出所有的排列方式，同样是用深度优先搜索，不过为了避免重复选择的情况，我们要保证两点：第一，所有数必须是数组中的，第二，数组中每个数只能用不多于也不少于一次。如果我们要单独写一个函数，来判断下一轮搜索该选择哪一个数就很麻烦了。这里有一个技巧，我们可以只将数两两交换，不过交换时只能跟自己后面的交换。
代码
public class solution {list
> res;public list> permute(int[] nums) {res = new linkedlist>();helper(nums, 0);return res;}public void helper(int[] nums, int i){// 找到转置完成后的解，将其存入列表中if(i == nums.length - 1){list list = new linkedlist();for(int j = 0; j < nums.length; j ){list.add(nums[j]);}res.add(list);}// 将当前位置的数跟后面的数交换，并搜索解for(int j = i; j < nums.length; j ){swap(nums, i , j);helper(nums, i 1);swap(nums, i, j);}}private void swap(int[] nums, int i, int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}
深度优先搜索
复杂度
时间 o(n) 空间 o(n) 递归栈
思路
我们还可以简单的使用深度优先搜索来解决这题。每一轮搜索选择一个数加入列表中，同时我们还要维护一个全局的布尔数组，来标记哪些元素已经被加入列表了，这样在下一轮搜索中要跳过这些元素。
代码
public class solution {list> res;boolean[] used;public list> permute(int[] nums) {res = new linkedlist>();used = new boolean[nums.length];list tmp = new linkedlist();helper(nums, tmp);return res;}private void helper(int[] nums, list tmp){if(tmp.size() == nums.length){list list = new linkedlist(tmp);res.add(list);} else {for(int idx = 0; idx < nums.length; idx ){// 遇到已经加过的元素就跳过if(used[idx]){continue;}// 加入该元素后继续搜索used[idx] = true;tmp.add(nums[idx]);helper(nums, tmp);tmp.remove(tmp.size()-1);used[idx] = false;}}}
}
given a collection of numbers that might contain duplicates, return all possible unique permutations.
for example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1].
深度优先搜索
复杂度
时间 o(n) 空间 o(n) 递归栈
思路
这题和上题的深度优先搜索很相似，区别在于：1、要先将数组排序，确保重复的元素是在一起的。2、除了不能加入之前出现过的元素之外，还不能加入本轮搜索中出现过的元素。如何判断哪些元素本轮出现过呢？我们加过一个数字并搜索后，在这一轮中把剩余的重复数字都跳过就行了，保证每一轮只有一个unique的数字出现。这和combination sum ii中跳过重复元素的方法是一样的，注意要判断nums[i] == nums[i 1]，因为for循环结束时i还会额外加1，我们要把i留在最后一个重复元素处。
代码
public class solution {list> res;boolean[] used;public list> permuteunique(int[] nums) {res = new linkedlist>();used = new boolean[nums.length];arrays.sort(nums);list tmp = new linkedlist();helper(nums, tmp);return res;}private void helper(int[] nums, list tmp){if(tmp.size() == nums.length){list list = new linkedlist(tmp);res.add(list);} else {for(int idx = 0; idx < nums.length; idx ){// 遇到已经加过的元素就跳过if(used[idx]){continue;}// 加入该元素后继续搜索used[idx] = true;tmp.add(nums[idx]);helper(nums, tmp);tmp.remove(tmp.size()-1);used[idx] = false;// 跳过本轮的重复元素，确保每一轮只会加unique的数字while(idx < nums.length - 1 && nums[idx] == nums[idx 1]){idx ;}}}}
}
总结
以上是凯发k8官方网为你收集整理的[leetcode] permutations 全排列的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得凯发k8官方网网站内容还不错，欢迎将凯发k8官方网推荐给好友。
