LeetCode by python——全排列 II（Permutations II）

ゞ浴缸里的玫瑰 2022-05-14 13:38 185阅读 0赞

# 题目： #

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

**示例:**

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

# 思路： #

假如你是从开始一题一题做下来的人，这道题应该轻而易举就搞定了。首先说下，这道题和上到全排列有什么不一样：

*  数字集中有重复数字

说下我们需要注意什么：

*  数字集是无序的
 *  数字集含有负数

接下来就是将下思路了，有重复的数字，这种类似的题目在前面出现过一些，那么这里我采用的是和前面那些题目一样，记录每个数字的个数，然后遍历无重复数字集合，在每次添加数字到结果集时，都要判断该数字剩余数量是否大于零，添加完后，要对数量进行-1操作。

最后说明一下，不要在结果集那里求set，虽然这样比较简单，但是会超时。

# 代码： #

class Solution:
        def permute(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            if len(nums) == 0:
                return []
            self.numCnt1 = [0 for i in range(max(nums) + 1)]
            self.numCnt2 = []
            if min(nums) < 0:#负数另外用一个list存放数字的数量
                self.numCnt2 = [0 for i in range(-1*min(nums) + 1)]
            self.results = []
            self.cnt = len(nums)#存放集合大小
            nums1 = []
            #去除重复数字
            for num in nums:
                if num >= 0 and self.numCnt1[int(num)] == 0:
                    nums1.append(num)
                elif num < 0 and self.numCnt2[abs(num)] == 0:
                    nums1.append(num)
                if num >= 0:
                    self.numCnt1[num] += 1
                else:
                    self.numCnt2[abs(num)] += 1
    
            for index, num in enumerate(nums1):
                tempResult = []
                tempResult.append(num)
                self.numCntMinus(num)
                self.helper(nums1, tempResult)
                self.numCntPlus(num)
            return self.results
        def helper(self,nums,tempResult):
            tempResult1 = copy.deepcopy(tempResult)
            if len(tempResult) == self.cnt:
                self.results.append(tempResult1)
            else:
                for num in nums:
                    if self.judgeCnt(num) > 0:#判断是否还有该数字
                        tempResult1.append(num)
                        self.numCntMinus(num)
                        self.helper(nums, tempResult1)
                        self.numCntPlus(num)
                        tempResult1.pop()
        def judgeCnt(self,num):
            '''
            判断该数字剩余数量是否大于零
            :param num:
            :return:
            '''
            if num >= 0 and self.numCnt1[num] > 0:
                return True
            elif num < 0 and self.numCnt2[num] > 0:
                return True
            return False
        def numCntPlus(self,num):
            '''
            对数字数量进行+1
            :param num:
            :return:
            '''
            if num >= 0:
                self.numCnt1[num] += 1
            else:
                self.numCnt2[num] += 1
        def numCntMinus(self, num):
            """
            对数字数量进行-1
            :param num:
            :return:
            """
            if num >= 0:
                self.numCnt1[num] -= 1
            else:
                self.numCnt2[num] -= 1
    if __name__ =="__main__":
        res = Solution()
        print(res.permute([3,3,0,3]))
        pass