47. Permutations II ?
题目：Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
have the following unique permutations:
, , and .
链接： http://leetcode.com/problems/permutations-ii/
4/15/2017
自己的做法是错的，但是按照别人的改一下就对了。
自己的错误做法，一直到才有test case挂的情况，正确是有630个解，我的算法有696个解。
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
if (nums.length == 0) return ret;
Arrays.sort(nums);
enumerate(nums, ret, 0);
return ret;
}
private void enumerate(int[] nums, List<List<Integer>> ret, int pos) {
if (pos == nums.length) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
list.add(nums);
}
ret.add(list);
return;
}
for (int i = pos; i < nums.length; i++) {
if (i != pos && (nums == nums || nums == nums)) continue;
exchange(nums, pos, i);
enumerate(nums, ret, pos + 1);
exchange(nums, i, pos);
}
}
private void exchange(int[] nums, int i, int j) {
int tmp = nums;
nums = nums;
nums = tmp;
}
}
按照讨论修改了几句，也不需要sort，10ms, 45%
https://discuss.leetcode.com/topic/36221/share-my-java-code-with-detailed-explanantion
我不能解释为什么会这样，不过我的猜想是即使最开始已经sort过了，在中间的各种交换之后也许不能保证在recursive function之内相同元素是相邻的了。
很多算法题有去重复的要求，有时候需要判断相邻元素，有时候要用set。什么情况用啥呢？
这道题让我意识到需要理解其他更普遍的backtracking permutation的算法
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
if (nums.length == 0) return ret;
enumerate(nums, ret, 0);
return ret;
}
private void enumerate(int[] nums, List<List<Integer>> ret, int pos) {
if (pos == nums.length) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
list.add(nums);
}
ret.add(list);
return;
}
Set<Integer> appeared = new HashSet<>();
for (int i = pos; i < nums.length; i++) {
if (!appeared.add(nums)) continue;
exchange(nums, pos, i);
enumerate(nums, ret, pos + 1);
exchange(nums, i, pos);
}
}
private void exchange(int[] nums, int i, int j) {
int tmp = nums;
nums = nums;
nums = tmp;
}
}
Princeton Introduction to Programming in Java里对permutation有很多介绍，可惜没有跟这道题一样的。有机会一定看看：
http://introcs.cs.princeton.edu/java/23recursion/
别人的做法：
visited的意义?在当前层还是递归层？
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
Arrays.sort(nums);
boolean[] visited = new boolean;
permuteUnique(res, new ArrayList<Integer>(), visited, nums);
return res;
}
private void permuteUnique(List<List<Integer>> res, List<Integer> onePerm, boolean[] visited, int[] nums) {
if (onePerm.size() == nums.length) {
res.add(new ArrayList<>(onePerm));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited || (i > 0 && nums == nums && visited)) {
continue;
}
visited = true;
onePerm.add(nums);
permuteUnique(res, onePerm, visited, nums);
onePerm.remove(onePerm.size() - 1);
visited = false;
}
}
}
更多讨论：
https://discuss.leetcode.com/category/55/permutations-ii
4/22/2017
算法班
跟前面别人的算法一样，注意第26行的!visited是一定要有的，为什么，当相同值的时候如果想要加入当前元素，必须保证前面相同值已经在permutation里面了，这样，他们的相对位置才能始终一致。
如果没有这个条件，碰到相同元素后面的就加不进去了，所以permutation永远不会到permutation.size() == nums.length，结果为空list
class Solution {
/**
* @param nums: A list of integers.
* @return: A list of unique permutations.
*/
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
if (nums == null) return ret;
boolean[] visited = new boolean;
Arrays.sort(nums);
ArrayList<Integer> permutation = new ArrayList<Integer>();
helper(ret, permutation, nums, visited);
return ret;
}
private void helper(List<List<Integer>> ret,
ArrayList<Integer> permutation,
int[] nums,
boolean[] visited) {
if (permutation.size() == nums.length) {
ret.add(new ArrayList<Integer>(permutation));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited || (i > 0 && !visited && nums == nums)) continue;
visited = true;
permutation.add(nums);
helper(ret, permutation, nums, visited);
permutation.remove(permutation.size() - 1);
visited = false;
}
}
}
页:
[1]