LC 47. Permutations II

https://leetcode.com/problems/permutations-ii/

我过去写全排列使用的是递归算法,但是这种算法似乎不太能够很好地用于去重。 另外一个全排列算法其实是DFS算法,每次从剩余的数字集合里面选出一个,直到全部选完。 这种算法比较适合这题。

这里我先贴一下两种全排列的算法。dfs版本的好处在于,每次可以根据之前的状态进行数字挑选,但是不如递归版本那么紧凑和高效。

# 递归版本
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        nums.sort()
        res = []

        def f(nums, idx):
            if idx == len(nums):
                res.append(list(nums))
                return
            for i in range(idx, len(nums)):
                nums[idx], nums[i] = nums[i], nums[idx]
                f(nums, idx + 1)
                nums[idx], nums[i] = nums[i], nums[idx]

        f(nums, 0)
        return res

# DFS版本
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort()
        n = len(nums)
        used = [False] * n

        def dfs(path):
            if len(path) == n:
                ans.append(path.copy())
                return

            for j in range(n):
                if not used[j]:
                    used[j] = True
                    path.append(nums[j])
                    dfs(path)
                    path.pop()
                    used[j] = False

        dfs([])
        return ans

说回这题,无论如何都需要先对整个数组排序,拿到排序之后的数组,考虑 [1,1,1,2,2]

所以算法逻辑是,在DFS算法的基础上:

直白地翻译成为代码就是下面这样的。我这里维护了一个字典用于统计每个数出现的次数。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)

        ans = []
        from collections import defaultdict

        def dfs(opts, path):
            # print(opts, path)
            if len(opts) == 0:
                ans.append(path.copy())
                return

            items = list(opts.items())
            for x, v in items:
                if path and path[-1] == x:
                    continue

                sz = len(path)
                for i in range(v):
                    opts[x] -= 1
                    if opts[x] == 0:
                        del opts[x]
                    path.extend([x] * (i + 1))
                    dfs(opts, path)
                    path = path[:sz]

                opts[x] = v

        opts = defaultdict(int)
        for x in nums:
            opts[x] += 1
        dfs(opts, [])
        ans.sort()
        return ans

和上面一样的思路,但是很明显官方给的 解答 实现更加精简高效。相当于给相同元素做了一个定序

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

        used = [0] * n
        ans = []

        def dfs(path):
            if len(path) == n:
                ans.append(path.copy())
                return

            for i in range(n):
                if used[i]:
                    continue
                if i > 0 and nums[i - 1] == nums[i] and not used[i - 1]:
                    continue

                used[i] = 1
                path.append(nums[i])
                dfs(path)
                path.pop()
                used[i] = 0

        dfs([])
        return ans