Permutations II (M)

題目

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

題意

求給定陣列的全排列，注意陣列中有重復元素，

思路

與 46. Permutations 相比，多了重復元素，只要在46解法基礎上加上相應的限制即可，

1. 回溯法：
   • 使用hash：用一張hash表記錄整個搜索中對應下標的數是否已被使用，每一層遞回中再用一張hash表記錄當前遞回層次中已經插入過(又移除)的數字，每次操作都往已有序列后插入一個未被使用的數(既是整個搜索中未被使用，也是當前遞回中未被使用)，更新hash，遞回，再移除改數，更新hash，
   • 不使用hash：對于結果序列中的每一個位置index，它可能存放的數為nums從index到最后一個位置nums.length-1中的任意一個數，但要保證每次存放的都是不同的數，所以每次操作都從這(nums.length - index)個數中選出一個，并判斷該數是否已經存放過，若沒有則放到當前空位，再對右邊的空位進行遞回操作，
2. 結合 31. Next Permutation 來實作全排列，

代碼實作

Java

回溯法無hash

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        permute(nums, 0, ans);
        return ans;
    }

    private void permute(int[] nums, int index, List<List<Integer>> ans) {
        if (index == nums.length - 1) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                list.add(nums[i]);
            }
            ans.add(list);
            return;
        }

        for (int i = index; i < nums.length; i++) {
            // 每次都要判斷該數是否已經使用過
            boolean flag = false;
            for (int j = index; j < i; j++) {
                if (nums[i] == nums[j]) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                continue;
            }

            swap(nums, index, i);
            permute(nums, index + 1, ans);
            swap(nums, index, i);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

回溯法hash

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        permute(nums, new boolean[nums.length], new ArrayList<>(), ans);
        return ans;
    }

    private void permute(int[] nums, boolean[] hash, List<Integer> list, List<List<Integer>> ans) {
        if (list.size() == nums.length) {
            ans.add(new ArrayList<>(list));
        }

        // 當前遞回中也要用一張hash表記錄已經插入過的數字
        Set<Integer> used = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!hash[i] && !used.contains(nums[i])) {
                used.add(nums[i]);
                list.add(nums[i]);
                hash[i] = true;
                permute(nums, hash, list, ans);
                hash[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}

nextPermutation

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        while (true) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                list.add(nums[i]);
            }
            ans.add(list);
            if (hasNextPermutation(nums)) {
                nextPermutation(nums);
            } else {
                break;
            }
        }
        return ans;
    }

    // 根據當前排列計算下一個排列 
    private void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        int j = nums.length - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        swap(nums, i, j);
        reverse(nums, i + 1, nums.length - 1);
    }

    // 判斷是否存在下一個排列，即判斷是否已經是完全逆序數列
    private boolean hasNextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        return i >= 0;
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left++, right--);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

JavaScript

回溯法無hash

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  let lists = []
  dfs(nums, 0, lists)
  return lists
}


let dfs = function (nums, index, lists) {
  if (index === nums.length) {
    lists.push([...nums])
    return
  }

  let used = new Set()
  for (let i = index; i < nums.length; i++) {
    if (!used.has(nums[i])) {
      used.add(nums[i]);
      [nums[index], nums[i]] = [nums[i], nums[index]]
      dfs(nums, index + 1, lists);
      [nums[index], nums[i]] = [nums[i], nums[index]]
    }
  }
}

回溯法hash

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  let lists = []
  dfs(nums, 0, [], lists, new Set())
  return lists
}

let dfs = function (nums, index, list, lists, record) {
  if (index === nums.length) {
    lists.push([...list])
    return
  }

  let used = new Set()
  for (let i = 0; i < nums.length; i++) {
    if (!record.has(i) && !used.has(nums[i])) {
      used.add(nums[i])
      record.add(i)
      list.push(nums[i])
      dfs(nums, index + 1, list, lists, record)
      list.pop()
      record.delete(i)
    }
  }
}

標籤：其他

上一篇：0046. Permutations (M)

下一篇：在tiny210開發板上安裝RTL8192EU無線模塊傳輸視頻總是掉線問題