leetcode31. Next Permutation算法与实现
一、题目描述
实现获取下一个排列的函数,算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列,则将数字重新排列成最小的排列(即升序排列)。
必须原地修改,只允许使用额外常数空间。
以下是一些例子,输入位于左侧列,其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
二、题目分析
一、什么是字典序中下一个更大的排列?
在纯数字序列中,下一个排列的理解较为简单,可以这样理解:
给定一个数字序列,如3,2,1,4,我们可以将其认为是数字3214,只要找出由这几位数字组成,且只比原排列大一些的那个数字就可以了,这里就是3241。
如果数组已经是最大了,比如3,2,1,那它的下一个排列就是1,2,3了。
二、如何找出下一个排列?
方法一:暴力排序法
找出给定数字的所有排列,将他们进行排序,这样自然就能找到下一个排列了。但很显然这种算法的计算量比较大,效率很低。
方法二:一遍循环法
观察序列,我们发现,实际上我们只需要从后向前数,找第一个降序的位置,再把这个降序数字和后面第一个比它大的位置交换即可。
下面给出具体例子:
例如此数组: 1,5,8,4,7,6,5,3,1
下一个排列: 1,5,8,5,7,6,4,3,1
观察可以发现,在给出的数组中,7之后的数字都是降序排列的,我们把7后面第一个比4大的数字放到最前面。这里就是把5和4做交换了。
然后让5后面的数字升序排列。
这样就得到了下一个数列
三、算法与代码分析
由上述的分析我们可以整理出解决这个问题时的整体步骤如下:
1. 判断数组是否只有一个或0个元素,若是,返回原值,若不是,进入2步骤
2. 找出第一个断点:从数组的最后一位往前查找,若找到一个数比它的前一个数大,则停止查找,该处即为断点。若查找直到数组中的第一个数字,说明数组已经到了最大值,直接返回该数组的重排。
3. 找出第二个断点:以第一个断点为界,从数组的最后一位往前查找,如果找到一个数比断点数字大,则停止查找,交换他们的值。
4. 将交换后的数组从第一个断点之后的所有数字进行重排。
具体代码实现(python):
1.判断数组是否只有一个或0个元素:
n = len(num)-1
if n <1:
return num
找出第一个断点,顺带判断数组是否已经时最大:
for i in range(n,-1,-1):
if num[i]>num[i-1]:
break
if i == 0:
num = num[::-1]
(如下图所示,这里给出一个数组最大时num[i]与num[i-1]的位置,在python中,num[-1]代表num数组中的倒数第一位。)
3.找出第一个断点后比断点数字大的那个数字,将它们进行交换:
for j in range(n,i-1,-1):
if num[j]>num[i-1]:
num[i-1],num[j]=num[j],num[i-1]
break
4.断点后的数字重排:
num[i:n+1] = num[n:i-1:-1]
四、整体代码
class Solution:
def nextPermutation(self,num):
n = len(num)-1
if n <1:
return num
else:
for i in range(n,-1,-1):
if num[i]>num[i-1]:
break
if i == 0:
num = num[::-1]
else:
for j in range(n,i-1,-1):
if num[j]>num[i-1]:
num[i-1],num[j]=num[j],num[i-1]
break
temp = num[n:i-1:-1]
num[i:n+1] = temp
return num