LeetCode47, 全排列进阶,如果有重复元素怎么办?

2020-07-30 来源: TechFlow2019 发布在  https://www.cnblogs.com/techflow/p/12640513.html

本文始发于个人公众号:TechFlow,原创不易,求个关注

今天是LeetCode第28篇,依然是全排列的问题。

如果对全排列不熟悉或者是最近关注的同学可以看一下上一篇文章:

LeetCode46 回溯算法求全排列,这次是真全排列

LeetCode就是喜欢这样,把类似的问题放在一起,让你刷的时候一起刷,从而更加深刻地理解。今天的问题同样是全排列,不过稍稍不同的是,我们有一个限制条件不一样,给定的元素当中可能存在重复。但是元素存在重复,我们并不想最后的结果也出现重复,这个时候应该怎么办?

举个例子,比如我们有一个排列是[1, 2, 2].

它的所有排列是[1, 2, 2], [2, 1, 2], [2, 2, 1],但是注意,在之前的做法当中,我们把所有的元素看成是unique的,但是现在这个条件被破坏了。显然我们需要在实现全排列的基础上解决这个问题。

无脑解决

解决的方法有两种,第一种是无脑解决。是的你没有看错,因为我们分析一下就会发现next_permutation循环的方法在这题当中仍然奏效,原因也很简单,因为我们每次用next_permutation求得字典序+1的下一个排列的时候,显然已经去除了重复元素的情况。为什么?因为同样元素换位置字典序是不会变化的。

比如下图当中,我们更换两个2的顺序,整个序列的字典序是没有变化的,要使得字典序变化一定要交换不同的元素。所以这个解法是可行的。

next_permutation是返回当前序列字典序+1的序列的算法,这个算法在之前的文章当中出现过,所以我就不赘述它的原理了,如果你不记得或者是忘记了的话,可以点击下方的链接回顾一下:

LeetCode 31:递归、回溯、八皇后、全排列一篇文章全讲清楚

这个解法和上一题的最后一个解法完全一样,连改动都不需要,我们直接把代码copy过来把函数名匹配上就可以提交了。这也是我说这道题无脑的原因。

class Solution:
    def get_next(self, nums: List[int]):
        """
        Do not return anything, modify nums in-place instead.
        """
        # 长度
        n = len(nums)
        # 记录图中i-1的位置
        pos = n - 1
        for i in range(n-1, 0, -1):
            # 如果降序破坏,说明找到了i
            if nums[i] > nums[i-1]:
                pos = i-1
                break
                
        for i in range(n-1, pos, -1):
            # 从最后开始找大于pos位置的
            if nums[i] > nums[pos]:
                # 先交换元素,在进行翻转
                nums[i], nums[pos] = nums[pos], nums[i]
                # 翻转[pos+1, n]区间
                nums[pos+1:] = nums[n:pos:-1]
                return False
        return True
        
        
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ret = []
        # 从小到大排序,获得最小排列
        nums = sorted(nums)
        ret.append(nums.copy())
        # 如果还有下一个排列则继续调用
        while not self.get_next(nums):
            # 要.copy()是因为Python中存储的引用,如果不加copy
            # 会导致当nums发生变化之后,ret中存储的数据也会变化
            ret.append(nums.copy())
        return ret

回溯法

显然重复之前的工作并不能让我们变得更强,所以我们还是要回到正解上来。在之前的文章我们知道,生成全排列的通常做法是使用回溯法。那么如果使用回溯法我们怎么解决重复元素的问题呢?

还是老惯例,我们要解决问题,首先来分析问题,我们知道重复的元素会干扰全排列生成的算法,那么它为什么会干扰,是怎么干扰的?

在回溯法当中,我们是顺序遍历位置,然后枚举放置的元素。于是我们大概可以想出两种可能导致重复的情况。

我们先来看情况1,情况1很简单,就是同一个位置放入同样元素的情况。比如我们原数组当中有两个4,我们在放置的过程当中放入第一个4和第二个4的情况是一样的。显然这就重复了,我们可以参考下下图,我们给当下所有的选择编号,选择2和选择3是等价的,两者只能选一个。

第二种情况也比较容易想明白,还是同样的例子,我们给数组当中的两个4编号,一个编号是,一个是,我们会发现对于两个位置,我们先放第一个再放第二个和先放第二个再放第一个是重复的

表面上来看情况是这两种,但是如果深入分析会发现这两种情况其实说的是一回事,结果出现重复都是由于全排列的时候元素出现不稳定造成的。

这里的“稳定“其实是一个排序算法当中的术语,我们经常会讨论某一个排序算法是稳定的,某一个不是。这个稳定是什么意思呢,其实就是指的元素的相对顺序。比如在上面这张图当中的两个4,如果在排序的结果当中,后面一个4有可能出现在第一个4的前面,那么就说明这个算法是不稳定的,同样,如果不会出现这样的情况,那么可以说这个算法是稳定的。

同样,如果我们能保证执行全排列的时候元素的稳定性,那么这个问题就解决了。表面上看这似乎是一个优化问题,其实不然,考察的是稳定性这个概念。

如果能想到稳定性这点,离解决已经很近了。我们要保证稳定性,也就是说对于当前元素,我们需要保证前面的同元素已经放置了,那么在一个排列中,相同元素的摆放位置应该是递增的。我们用map记录每一个元素最后一次摆放的位置,控制它在往下递归的过程当中递增即可。

比如当数组当中有两个4的时候,第一个4如果还没有摆放,那么第二个4也不能摆。但是由于我们在判断要不要摆放第二个4的时候,并不知道前面是否还有其他的4,所以我们只能倒过来,判断在摆放第一个4的时候,是不是已经放过了后面的4,如果是的话,那么这个操作不能执行。用语言描述这个逻辑有点绕,我们来看下图就明白了:

我们摆放了第一个4之后,map[4] = 4,记录的是摆放的4的下标,当我们枚举放置第一个4的时候,发现已经放置的4下标大于当前,说明非法,放置了会引起重复。

还有一个问题是当我们回溯的时候,需要重置map里的值,比如:

在一次递归当中,我们放置了两个4,放了第二个4之后,map[4] = 4,当我们回溯弹出第二个4的时候,这个时候的map[4]应该是多少?

答案不难,应该是1,也就是第一个4的下标。所以我们在递归的时候,在更新map之前,需要记录一下之前的值,方便回溯的时候恢复。

我们整理一下,思路可以得到代码:

class Solution:
    def dfs(self, nums, n, i, states, cur, ret, flag):
        if i == n:
            ret.append(cur.copy())
            return
        for p in range(n):                
            # 遍历所有元素
            # 如果p元素已经放置过了,或者是已经放置了更后面的同元素
            # 跳过
            if flag[p] or (nums[p] in states and states[nums[p]] >= p):
                continue
            # 当前位置放置p
            cur.append(nums[p])
            # 更新之前,记录之前的值
            tmp, states[nums[p]] = states[nums[p]] if nums[p] in states else -1, p
            # flag[p]置为True
            flag[p] = True
            # 递归
            self.dfs(nums, n, i+1, states, cur, ret, flag)
            # 回溯
            cur.pop()
            flag[p] = False
            # 恢复递归之前的值
            states[nums[p]] = tmp 
            # states.remove((i, nums[p]))
        
        
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ret = []
        n = len(nums)
        # 记录元素i有没有放置过
        flag = [False for _ in range(n)]
        self.dfs(nums, n, 0, {}, [], ret, flag)
        return ret

改进

上面这个方法其实有点复杂,理解起来有很多细节,一个比较蛋疼的点就是我们用了map去记录了位置,由于要更新map,所以还需要记录之前的值,还需要判断元素不在map当中的情况。并且map的查找存在开销,那么我们能不能不用map呢?

在想怎么不用map的替代方案之前,我们需要先搞清楚,我们为什么要使用map?

这个问题问的并不是一个充分问题,而是一个必要问题,不是用map解决了什么问题,而是我们为什么只能用map不可呢?

因为map是一个容器,它能存储数据。对于一个元素t来说,我们并不知道它在数组nums当中之前出现的位置是哪里,我们也并不知道这些之前出现的t有没有被放入当前的排列里。我们用map记录下t的下标,本质原因是这个。map只是我们实现这个功能的手段,不是目的。

所以我们如果不想使用map,必须要保证能够知道每一个元素的摆放位置才可以。要做到这点其实并不难,我们只需要对nums排序就好了。排序之后,所有相同的元素都会挨在一起。那么,对于位置p来说,我们只需要判断如果nums[p-1] 等于 nums[p]的话,必须要flag[p-1]等于true,也就是说对于元素v来说,它前面一位如果是v必须要放置好,才能放置当前的v,否则就是非法的。这样每一个v都限制前一个v,就保证了所有的v不会起冲突。这是一种链式限制的思想。

通过这种方法,我们就可以抛弃掉map的使用,进而极大地提升效率。

想清楚了原理之后,代码非常简单:

class Solution:
    def dfs(self, nums, n, i, cur, ret, flag):
        if i == n:
            ret.append(cur.copy())
            return
        for p in range(n):                
            # 遍历所有元素
            # 如果p元素已经放置过了,或者
            # 如果nums[p-1] == nums[p] 并且flag[p-1] 是False
            # 跳过
            if flag[p] or (p > 0 and nums[p-1] == nums[p] and not flag[p-1]):
                continue
            # 当前位置放置p
            cur.append(nums[p])
            # flag[p]置为True
            flag[p] = True
            # 递归
            self.dfs(nums, n, i+1, cur, ret, flag)
            # 回溯
            cur.pop()
            flag[p] = False
        
        
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ret = []
        n = len(nums)
        # 记录元素i有没有放置过
        nums = sorted(nums)
        flag = [False for _ in range(n)]
        self.dfs(nums, n, 0, [], ret, flag)
        return ret

你看,我们只需要排序,也不需要引入新的数据结构,就可以完美地解决这个问题。其实很多时候,解决问题的途径有很多种,能不能想到更好的解法除了取决于能力之外,更重要的还是对问题的理解。

这道题也是一个Medium的问题,总体来说难度并不大。如果可以不看标程,独立通过这道题,就说明对全排列这个问题的思考已经比较到位了。

今天的文章就是这些,如果觉得有所收获,请顺手点个关注或者转发吧,你们的举手之劳对我来说很重要。

相关文章