首页 > 代码库 > 47. Permutations II ?

47. Permutations II ?

2024-09-15 04:42:45   218人阅读

题目：

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].

链接： http://leetcode.com/problems/permutations-ii/

4/15/2017

自己的做法是错的，但是按照别人的改一下就对了。

自己的错误做法，一直到[1,0,2,0,1,-1,-1]才有test case挂的情况，正确是有630个解，我的算法有696个解。

 1 public class Solution {
 2     public List<List<Integer>> permuteUnique(int[] nums) {
 3         List<List<Integer>> ret = new ArrayList<>();
 4         if (nums.length == 0) return ret;
 5         Arrays.sort(nums);
 6         enumerate(nums, ret, 0);
 7         return ret;
 8     }
 9     private void enumerate(int[] nums, List<List<Integer>> ret, int pos) {
10         if (pos == nums.length) {
11             ArrayList<Integer> list = new ArrayList<Integer>();
12             for (int i = 0; i < nums.length; i++) {
13                 list.add(nums[i]);
14             }
15             ret.add(list);
16             return;
17         }
18         for (int i = pos; i < nums.length; i++) {
19             if (i != pos && (nums[i] == nums[pos] || nums[i] == nums[i - 1])) continue;
20             exchange(nums, pos, i);
21             enumerate(nums, ret, pos + 1);
22             exchange(nums, i, pos);
23         }
24     }
25     private void exchange(int[] nums, int i, int j) {
26         int tmp = nums[i];
27         nums[i] = nums[j];
28         nums[j] = tmp;
29     }
30 }

按照讨论修改了几句，也不需要sort，10ms, 45%

https://discuss.leetcode.com/topic/36221/share-my-java-code-with-detailed-explanantion

我不能解释为什么会这样，不过我的猜想是即使最开始已经sort过了，在中间的各种交换之后也许不能保证在recursive function之内相同元素是相邻的了。

很多算法题有去重复的要求，有时候需要判断相邻元素，有时候要用set。什么情况用啥呢？

这道题让我意识到需要理解其他更普遍的backtracking permutation的算法

 1 public class Solution {
 2     public List<List<Integer>> permuteUnique(int[] nums) {
 3         List<List<Integer>> ret = new ArrayList<>();
 4         if (nums.length == 0) return ret;
 5         enumerate(nums, ret, 0);
 6         return ret;
 7     }
 8     private void enumerate(int[] nums, List<List<Integer>> ret, int pos) {
 9         if (pos == nums.length) {
10             ArrayList<Integer> list = new ArrayList<Integer>();
11             for (int i = 0; i < nums.length; i++) {
12                 list.add(nums[i]);
13             }
14             ret.add(list);
15             return;
16         }
17         Set<Integer> appeared = new HashSet<>();
18         for (int i = pos; i < nums.length; i++) {
19             if (!appeared.add(nums[i])) continue;
20             exchange(nums, pos, i);
21             enumerate(nums, ret, pos + 1);
22             exchange(nums, i, pos);
23         }
24     }
25     private void exchange(int[] nums, int i, int j) {
26         int tmp = nums[i];
27         nums[i] = nums[j];
28         nums[j] = tmp;
29     }
30 }

Princeton Introduction to Programming in Java里对permutation有很多介绍，可惜没有跟这道题一样的。有机会一定看看：

http://introcs.cs.princeton.edu/java/23recursion/

别人的做法：

visited的意义?在当前层还是递归层？

 1 public class Solution {
 2     public List<List<Integer>> permuteUnique(int[] nums) {
 3         List<List<Integer>> res = new ArrayList<>();
 4         if (nums == null || nums.length == 0) {
 5             return res;
 6         }
 7         Arrays.sort(nums);
 8         boolean[] visited = new boolean[nums.length];
 9         permuteUnique(res, new ArrayList<Integer>(), visited, nums);
10         return res;
11     }
12     
13     private void permuteUnique(List<List<Integer>> res, List<Integer> onePerm, boolean[] visited, int[] nums) {
14         if (onePerm.size() == nums.length) {
15             res.add(new ArrayList<>(onePerm));
16             return;
17         }
18         for (int i = 0; i < nums.length; i++) {
19             if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && visited[i - 1])) {
20                 continue;
21             }
22             visited[i] = true;
23             onePerm.add(nums[i]);
24             permuteUnique(res, onePerm, visited, nums); 
25             onePerm.remove(onePerm.size() - 1);
26             visited[i] = false;
27         }
28     }
29 }

更多讨论：

https://discuss.leetcode.com/category/55/permutations-ii 

47. Permutations II ?


联系
我们