LeetCode解题报告(46，47)--排列

发表于 标签 ，

46. Permutations

原题如下：

Given a collection of distinct numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

题目要求列出给定的不重复数字的所有排列结果。解题方法有两种。下面分别讲述。

方法一

第一种方法每次取一个数字，将数字插入现有的排列中形成新的排列，然后重复上面的过程直到所有数字都被取完。

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        for num in nums:
            new_result = []
            for seq in result:
                for i in xrange(len(seq)+1):
                    new_result.append(seq[:i]+[num]+seq[i:])
            result = new_result
        return result

方法二

第二种方法采用回溯法。将当前数字与后面的数字逐一交换，当与某一数字交换后，然后移动到下一个数字重复上面的操作。实现具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        self.helper(nums,0,result)
        return result
        
    def helper(self, nums, begin, result):
        n = len(nums)
        if begin == n:
            tmp = nums[:]
            result.append(tmp)
            return
        
        for i in xrange(begin,n):
            nums[begin],nums[i] = nums[i], nums[begin]
            self.helper(nums,begin+1,result)
            nums[begin],nums[i] = nums[i], nums[begin]

47. Permutations II

原题如下：

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

For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1].

这道题目的要求与上一道一样，只是在上面的基础上添加了存在重复数字的约束条件。 上面提到回溯法在这里不适用了（即使判定交换的元素是否相等），比如说对于[1,2,3,3]就不正确了。

采用方法一的直接插入法，从后往前插，遇到与当前要插入数字相同的数字时就终止当前排列的插入，进行下一个排列的插入。实现的具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        for num in nums:
            new_result = []
            for seq in result:
                n = len(seq)
                for i in xrange(n,-1,-1):
                    if i < n and seq[i] == num:
                        break
                    new_result.append(seq[:i]+[num]+seq[i:])
            result = new_result
        return result