Lintcode190 Next Permutation II solution 题解
发布在lintcode2018年1月28日view:167
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

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

给定一个若干整数的排列,给出按正数大小进行字典序从小到大排序后的下一个排列。

如果没有下一个排列,则输出字典序最小的序列。

【题目链接】

www.lintcode.com/en/problem/next-permutation-ii/

【题目解析】

首先找到需要变大的那一位。因为求的是next permutation,所以增大位数要尽量靠右边同时增大的数值要尽量小。具体方法如下:

1) 从数组尾部开始,依次找每一位数离它最近的比它小的数的位置(即要变大的位置),记录下这个数和离它最近的比它小的数的index。每一位数得到的结果都和之前保存的结果做比较,保留index最大的要变大的位置和找到这个位置的数的位置,当要变大的位置相同时,保留数值较小的找到这个位置的数的位置。

2) 遍历完整个数组后,根据得到的结果,将要变大位置的数和找到这个位置的数交换位置,并返回变大的位置

3) 将数组从变大的位置的后一位开始从小到大排序即可。这里因为要求inplace所以用了bubble sort,若可以用额外空间还能用更快的排序方法。

【参考答案】

www.jiuzhang.com/solutions/next-permutation-ii/

作者:程风破浪会有时 链接:https://www.jianshu.com/p/308259d01290 來源:简书 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN
lintcode

lintcode题解

我的收藏