下一个排列
问题简述
给定一个整数数组,求该数组的下一个排列。
注意:完全逆序的下一个排列是正序。
要求:原地修改数组。
思路
为了使下一个排列更大,一个方法是将一个左边的「较小数」与一个右边的「较大数」交换;而为了使变大的幅度最小,需要让这个「较小数」尽量靠右,而「较大数」尽可能小。
具体实现:
找左边界:从后往前遍历,找到第一个
l
使a[l]
小于a[l + 1]
,此时必有a[l+1:]
为逆序;找右边界:再次从后往前遍历,找到第一个大于
a[l]
的位置r
;因为a[l+1:]
,所以j
依次遍历即可,此时a[l+1:]
依然为逆序;交换
a[l]
和a[r]
;将
a[l+1:]
倒序;
第 4 步说明:
在第 3 步交换
a[l]
和a[r]
后,无论a[l+1:]
无论怎么调整,都是比原来更大的排列,而其中最小的排列就是a[l+1:]
为顺序的情况,又因为此时a[l+1:]
正好为逆序,所以将其做倒置即可;
Last updated