P170 包含重复元素的数组排列

描述#

这个题目说的是，给你一个整数数组，数组中可能包含重复元素，你要返回这个数组所有不同的排列。

比如说，给你的数组是：
[0, 1, 0]
由 [0, 1, 0] 构成的不同排列只有 3 种，分别是：
[0, 0, 1]
[0, 1, 0]
[1, 0, 0]

相关视频：数组的全排列，数组的下一个排列

代码#

public class AlgoCasts {

  ////////// HashSet Version //////////
  private void permuteRec(List<Integer> nums, int start,
                          Set<List<Integer>> result) {
    if (start == nums.size()) {
      result.add(new ArrayList<>(nums));
    } else {
      for (int i = start; i < nums.size(); ++i) {
        Collections.swap(nums, i, start);
        permuteRec(nums, start + 1, result);
        Collections.swap(nums, i, start);
      }
    }
  }

  // Time: O(n*n!), Space: O(n)
  public List<List<Integer>> permuteUniqueUsingHashSet(int[] nums) {
    if (nums == null || nums.length == 0) return new ArrayList<>();
    Set<List<Integer>> result = new HashSet<>();

    List<Integer> list = new ArrayList<>();
    for (int num: nums) list.add(num);

    permuteRec(list, 0, result);
    return new ArrayList<>(result);
  }

  ////////// Counter Version //////////
  private void permuteRec(List<Integer> list, int n, List<List<Integer>> result,
                          Map<Integer, Integer> counter) {
    if (n <= 0) {
      result.add(new ArrayList<>(list));
    } else {
      for (Map.Entry<Integer, Integer> e: counter.entrySet()) {
        int cnt = e.getValue();
        if (cnt <= 0) continue;
        list.add(e.getKey());
        e.setValue(cnt-1);
        permuteRec(list, n-1, result, counter);
        e.setValue(cnt);
        list.remove(list.size()-1);
      }
    }
  }

  // Time: O(n*n!), Space: O(n)
  public List<List<Integer>> permuteUniqueUsingCounter(int[] nums) {
    if (nums == null || nums.length == 0) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();

    Map<Integer, Integer> counter = new HashMap<>();
    for (int num: nums) {
      int cnt = counter.getOrDefault(num, 0);
      counter.put(num, cnt+1);
    }

    List<Integer> list = new ArrayList<>();
    permuteRec(list, nums.length, result, counter);
    return result;
  }

  ////////// NextPermutation Version //////////
  private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
  }

  private List<Integer> toList(int[] nums) {
    List<Integer> list = new ArrayList<>(nums.length);
    for (int num: nums) list.add(num);
    return list;
  }

  // Time: O(n), Space: O(1)
  private boolean nextPermutation(int[] nums) {
    int n = nums.length;
    int p = n - 2;
    while (p >= 0 && nums[p] >= nums[p+1]) --p;

    if (p >= 0) {
      int i = n - 1;
      while (i > p && nums[i] <= nums[p]) --i;
      swap(nums, i, p);
    }
    for (int i = p+1, j = n-1; i < j; ++i, --j)
      swap(nums, i, j);
    return p != -1;
  }

  // Time: O(n*n!), Space: O(1)
  public List<List<Integer>> permuteUniqueUsingNextPermutation(int[] nums) {
    if (nums == null || nums.length == 0) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    result.add(toList(nums));
    while (nextPermutation(nums))
      result.add(toList(nums));
    return result;
  }

}