细语呢喃

技术改变生活

0%

leetcode 全排列详解

发表于 分类于 ， 阅读次数： 评论数：

本文为leetcode 全排列的详解，包括：

  • 31 Next Permutation
  • 46 Permutations
  • 47 Permutations II
  • 60 Permutation Sequence

一、STL next_permutation剖析

C++ STL中，有next_permutation可以直接调用，但是这样做题就没意思啦。

那么STL的next_permutation是怎么实现的呢？

下面的摘自wiki百科：

  1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
  2. Find the largest index l such that a[k] < a[l]. Since k+1 is such an index, l is well defined and satisfies k < l.
  3. Swap a[k] with a[l].
  4. Reverse the sequence from a[k+1] up to and including the last element a[n].

第一步找出一个k，使得k之后的为递减序列。（k之后的就没有全排列的结果了。想一下4321这种，都是逆序的）

接下来，我们需要找到一个最大的下标L使得 a[k]<a[L]，交换a[k]和a[L] （就是说递减序列中比a[k]大的最小的元素， 这样和位置k的进行交换，位置k之后的就又有全排列了）

最后对k+1之后的逆置即可（在纸上试试），这样就变成了升序。

eg: 1 4 3  2  k=0 L=3  swap-> 2431 逆置-> 2134

二、题解

31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

题目地址：leetcode Next Permutation

题目大意：给定一串整数，要求求出它的下一个排列，如1,2,3->1,3,2    3,2,1->1,2,3

思路：见上面的剖析

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2, j = nums.size() - 1;
        for(; i >= 0; --i)
            if(nums[i] < nums[i + 1])
                break;
        
        if(i < 0){
            reverse(nums.begin(), nums.end());
            return;
        }
        
        for(; j > i; --j)
            if(nums[i] < nums[j])
                break;
        
        swap(nums[i], nums[j]);
        reverse(nums.begin() + i + 1, nums.end());
    }
};

Java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    private void reverse(int[] nums, int start) {
        for (int i = start, j = nums.length - 1; i < j; i++, j--)
            swap(nums, i, j);
    }
    
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2, j = i + 1;
        for (; i >= 0 && nums[i] >= nums[i + 1]; i--) ;
        if (i < 0) {
            Arrays.sort(nums);
            return;
        }
        for (; j >= 0 && nums[i] >= nums[j]; j--) ;
        swap(nums, i, j);
        reverse(nums, i + 1);
    }
}


 

Python 

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 nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 2
        while i >= 0:
            if nums[i] < nums[i + 1]: break
            i -= 1
        if i < 0:
            nums.sort()
            return
        
        j = len(nums) - 1
        while i < j:
            if nums[i] < nums[j]:
                break
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = nums[i + 1:][::-1]

 

 

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].

题目地址：leetcode Permutations

题目大意: 给定一个不重复的数组，求全排列

思路：

可以用上面的STL next_permutation思想，也可以递归解决。

递归的想法是：nums的全排列相当于：

nums[0] + permute(nums  nums[0])  # 表示除了0以外的数的全排列

nums[1] + permute(nums  nums[1])

....

nums[n-1] + permute(nums  nums[n-1])

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
	void dfs(int cur, vector<int>& nums, vector<vector<int>> &ans) {
		if (cur == nums.size() - 1) {
			ans.push_back(nums);
			return;
		}
                //0...cur - 1都固定了
		for (int i = cur; i < nums.size(); i++) {
			swap(nums[cur], nums[i]);
			dfs(cur + 1, nums, ans);
			swap(nums[cur], nums[i]);
		}
	}

public:
	vector<vector<int>> permute(vector<int>& nums) {
		vector<vector<int>> ans;
		dfs(0, nums, ans);
		return ans;
	}
};

Java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    private void dfs(int cur, int[] nums, List<List<Integer>> ans) {
        if (cur == nums.length - 1) {
            List<Integer> res = new ArrayList<>();
            for (int num : nums) res.add(num);
            ans.add(res);
            return;
        }
        for (int i = cur; i < nums.length; i++) {
            swap(nums, i, cur);
            dfs(cur + 1, nums, ans);
            swap(nums, i, cur);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        dfs(0, nums, ans);
        return ans;
    }
}

 

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].

题目地址：leetcode Permutations II

题目大意：给定一个可能包含重复数字的数组，求全排列，要求去重。

思路

方法1，去重：

什么时候会产生重复呢？

注意，上面一题中，我们每次都让0...start - 1固定，然后交换nums[i]和nums[start]，接着继续递归下一层，然后恢复交换。

比如nums[i]有重复的元素，它之前的重复元素已经交换到start这个位置，那么之后nums[i]也要交换到start这个位置的话，那必然是重复的，因此我们可以记录一个数是不是被交换到start这个位置了。

只判断根据nums[i]和nums[start]是否相同判断是否重复是不够的，因为比如start的值为2，一开始交换到start的值为1，然后下一次交换过去的为1，两次都是判断2！=1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    void dfs(int start, vector<int> &nums, vector<vector<int>> &ans){
        if(start == nums.size() - 1){
            ans.push_back(nums);
            return;
        }
        unordered_set<int> vis;
        for(int i = start; i < nums.size(); ++i){
            if(vis.find(nums[i]) != vis.end()) continue;
            vis.insert(nums[i]);
            swap(nums[i], nums[start]);
            dfs(start + 1, nums, ans);
            swap(nums[i], nums[start]);
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        dfs(0, nums, ans);
        return ans;
    }
};

 

方法2， STL的next_permutation思想：

第一步找出一个k，使得k之后的为递减序列，如果k<0说明已经都是递减的了，就是说最后一个，递推结束。

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
	bool next_permutation(vector<int> &nums) {
		int i = nums.size() - 2;
		for (; i >= 0 && nums[i] >= nums[i + 1]; i--);
		if (i < 0) return false;
		int j = nums.size() - 1;
		for (; j >= 0 && nums[i] >= nums[j]; j--);
		swap(nums[i], nums[j]);
		reverse(nums.begin() + i + 1, nums.end());
		return true;
	}
public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		vector<vector<int>> ans;
		sort(nums.begin(), nums.end());
		do {
			ans.push_back(nums);
		} while (next_permutation(nums));
		return ans;
	}
};

Java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    private void reverse(int[] nums, int start) {
        for (int i = start, j = nums.length - 1; i < j; i++, j--)
            swap(nums, i, j);
    }

    private boolean next_permutation(int[] nums) {
        int i = nums.length - 2, j = i + 1;
        for (; i >= 0 && nums[i] >= nums[i + 1]; i--) ;
        if (i < 0) return false;
        for (; j >= 0 && nums[i] >= nums[j]; j--) ;
        swap(nums, i, j);
        reverse(nums, i + 1);
        return true;
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        do {
            List<Integer> res = new ArrayList<>();
            for (int num : nums) res.add(num);
            ans.add(res);
        } while (next_permutation(nums));
        return ans;
    }
}

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def next_permutation(self, nums):
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i < 0: return False
        j = len(nums) - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
        nums[:] = nums[:i + 1] + nums[:i:-1]
        return True

    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        ans = [nums[:]]
        while self.next_permutation(nums):
            ans.append(nums[:])
        return ans

 

60. Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):

"123" "132" "213" "231" "312" "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

题目地址：leetcode Permutation Sequence

题目大意：给定n和k，求1~n中能组成的排列中的第k个排列。

思路：难道要像上面几题，不断都next_permutation？ 答案显然是否定的。

其实对于每个排列，我们算得出来。

1~n的排列数有n! ，但如果我们第一个位置上放1，那么有(n-1)!种排列。

故，对于k，首先确定第一个数放几，然后第二个数……，一直到第n个数。

C++

对于放置的第cnt个数，我们有： j = k / (n - 1)! （算出应该放第几个） k = k %(n - 1)!（k剩余多少个）

下面代码首先k -= 1， 这是为了让k是从0开始的，便于除法取mod。(比如k==（n-1)!，此时位置j应该恰好可以用，如k=2, (n-1)!= 2的时候，2/2=1，但其实第一个数就可以覆盖到了。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
	string getPermutation(int n, int k) {
		vector<int> count(n + 1, 1);
		vector<int> nums(n, 1);
		for (int i = 2; i <= n; ++i) {
			count[i] = i * count[i - 1];
			nums[i - 1] = i;
		}
		
		--k;
		string ans;
		for (int i = n; i >= 1; --i) { //第i个位置
			int j = k / count[i - 1]; //第j个数
			k = k % count[i - 1];
			ans += nums[j] + '0';
			nums.erase(nums.begin() + j);
		}
		return ans;
	}
};

 

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        nums = [i for i in range(1, n + 1)]
        count = [1] * (n + 1)
        for i in range(2, n + 1):
            count[i] = count[i - 1] * i

        k -= 1
        ans = []
        for i in range(n, 0, -1):
            pos = k // count[i - 1]
            k = k % count[i - 1]
            ans.append(str(nums[pos]))
            nums.pop(pos)
        return ''.join(ans)

 

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~