Permutations II

描述

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

next_permutation()

直接使用std::next_permutation()，代码与上一题相同。

重新实现next_permutation()

重新实现std::next_permutation()，代码与上一题相同。

递归

递归函数permute()的参数p，是中间结果，它的长度又能标记当前走到了哪一步，用于判断收敛条件。

扩展节点，每次从小到大，选一个没有被用光的元素，直到所有元素被用光。

本题不需要判重，因为状态装换图是一颗有层次的树。

  1. // Permutations II
  2. // 深搜，时间复杂度O(n!)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<List<Integer>> permuteUnique(int[] nums) {
  5.         Arrays.sort(nums);  // 必须排序
  6.         List<List<Integer>> result = new ArrayList<>(); // 最终结果
  7.         List<Integer> path = new ArrayList<>(); // 中间结果
  9.         // 记录每个元素的出现次数
  10.         HashMap<Integer, Integer> counterMap = new HashMap<>();
  11.         for (int i : nums) {
  12.             counterMap.put(i, counterMap.getOrDefault(i, 0) + 1);
  13.         }
  14.         // 将HashMap里的pair拷贝到一个数组里
  15.         Pair[] counters = new Pair[counterMap.size()];
  16.         int i = 0;
  17.         for (Map.Entry<Integer, Integer> entry : counterMap.entrySet()) {
  18.             counters[i++] = new Pair(entry.getKey(), entry.getValue());
  19.         }
  20.         Arrays.sort(counters);
  22.         // 每个元素选择了多少个
  23.         HashMap<Integer, Integer> selected = new HashMap<>();
  24.         for (Pair p : counters) {
  25.             selected.put(p.key, 0 );
  26.         }
  28.         n = nums.length;
  29.         permute(counters, selected, path, result);
  30.         return result;
  31.     }
  33.     private int n;
  35.     void permute(Pair[] counters, HashMap<Integer,Integer> selected,
  36.                  List<Integer> path, List<List<Integer>> result) {
  37.         if (n == path.size()) {  // 收敛条件
  38.             result.add(new ArrayList<>(path));
  39.         }
  41.         // 扩展状态
  42.         for (Pair counter : counters) {
  43.             if (selected.get(counter.key) < counter.value) {
  44.                 path.add(counter.key);
  45.                 selected.put(counter.key, selected.get(counter.key) + 1);
  46.                 permute(counters, selected, path, result);
  47.                 path.remove(path.size() - 1);
  48.                 selected.put(counter.key, selected.get(counter.key) - 1);
  49.             }
  50.         }
  51.     }
  52.     static class Pair implements Comparable<Pair> {
  53.         int key;
  54.         int value;
  55.         public Pair(int key, int value) {
  56.             this.key = key;
  57.             this.value = value;
  58.         }
  60.         @Override
  61.         public int compareTo(Pair o) {
  62.             if (this.key < o.key) return -1;
  63.             else if (this.key > o.key) return 1;
  64.             else {
  65.                 return this.value - o.value;
  66.             }
  67.         }
  68.     }
  69. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/brute-force/permutations-ii.html