【题目描述】
Given a list of integers, which denote a permutation.Find the next permutation in ascending order.
Notice:The list may contains duplicate integers.
给定一个整数数组来表示排列，找出其之后的一个排列。
注意:排列中可能包含重复的整数
【题目链接】
【题目解析】
找下一个升序排列，C++ STL 源码剖析一书中有提及，Permutations 一小节中也有详细介绍，下面简要介绍一下字典序算法：
从后往前寻找索引满足 a[k] < a[k + 1], 如果此条件不满足，则说明已遍历到最后一个。
从后往前遍历，找到第一个比a[k]大的数a[l], 即a[k] < a[l].
交换a[k]与a[l].
反转k + 1 ~ n之间的元素。
由于这道题中规定对于[4,3,2,1], 输出为[1,2,3,4], 故在第一步稍加处理即可。
【参考答案】
评论
发表评论