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,31,3,2
3,2,11,2,3
1,1,51,5,1

题目地址:leetcode Next Permutation

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

思路:见上面的剖析

C++

Java

 

 Python

 

 

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++

Java

 

 

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.

 

 

方法2, STL的next_permutation思想:

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

C++

Java

Python

 

 


 

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,但其实第一个数就可以覆盖到了。)

 

Python

 

 

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

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 全排列详解
本文地址:https://www.hrwhisper.me/leetcode-permutations/

打赏一杯咖啡钱呗

Leetcode . permalink.

4 thoughts on “leetcode 全排列详解

  1. STL 的算法赞啊。 参考你的写了篇全排列BLOG有空给我指点一下啊http://www.zhuangjingyang.com/%E7%AA%81%E7%A0%B4%E5%85%A8%E6%8E%92%E5%88%97full_permutation/

Leave a Reply

Your email address will not be published. Required fields are marked *