133 - 47 全排列2

题目

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]

解答

https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-jian-zhi-deng-jie-ji-chu-quan-pai-lie-by-ge/

const helper = function(nums, level, res) {
  if (level === nums.length) {
    res.push([...nums])
    return
  }
  const map = new Map()
  for (let i = level; i < nums.length; i++) {
    if (!map.get(nums[i])) {
      map.set(nums[i], true);
      [nums[i], nums[level]] = [nums[level], nums[i]]
      helper(nums, level + 1, res);
      [nums[i], nums[level]] = [nums[level], nums[
        i]]
    }
  }
}
var permuteUnique = function(nums) {
  if (nums.length === 0) {
    return []
  } else if (nums.length === 1) {
    return [
      [nums[0]]
    ]
  }
  nums.sort((a, b) => a - b)
  const res = []
  helper(nums, 0, res)
  return res
};

Runtime: 72 ms, faster than 86.35% of JavaScript online submissions for Permutations II.

Memory Usage: 37.8 MB, less than 22.22% of JavaScript online submissions for Permutations II.

https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return []
        nums.sort()
        used = [False]*len(nums)
        res = []
        Solution._dfs(self, nums, 0, [], used, res)
        return res

    def _dfs(self, nums, index, pre, used, res):
        if index == len(nums):
            res.append(pre.copy())
            return
        for i in range(len(nums)):
            if not used[i]:
                if i > 0 and nums[i-1] == nums[i]and not used[i-1]:
                    continue
                used[i] = True
                pre.append(nums[i])
                Solution._dfs(self, nums, index+1, pre, used, res)
                pre.pop()
                used[i] = False

Runtime: 56 ms, faster than 97.36% of Python3 online submissions for Permutations II.

Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Permutations II.

把函数放在里面，就可以少传一些参数了。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return []
        nums.sort()
        res = []

        def _dfs(nums, pre):
            if not nums:
                res.append(pre)
                return
            for i in range(len(nums)):
                if i > 0 and nums[i-1] == nums[i]:
                    continue
                _dfs(nums[:i]+nums[i+1:], pre+[nums[i]])

        _dfs(nums, [])
        return res

Runtime: 56 ms, faster than 97.36% of Python3 online submissions for Permutations II.

Memory Usage: 13.1 MB, less than 95.56% of Python3 online submissions for Permutations II.

func permuteUnique(nums []int) [][]int {
    if len(nums) == 0 {
        return nil
    }
    sort.Ints(nums)
    ans := make([][]int, 0)
    dfs(nums, nil, &ans)
    return ans
}
func dfs(nums []int, prev []int, ans *[][]int) {
    if len(nums) == 0 {
        *ans = append(*ans, append([]int{}, prev...))
        return
    }
    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        dfs(append(append([]int{}, nums[:i]...), nums[i+1:]...), append(prev, nums[i]), ans)
    }
}

Runtime: 8 ms, faster than 95.61% of Go online submissions for Permutations II.

Memory Usage: 7.9 MB, less than 50.00% of Go online submissions for Permutations II.