【题目描述】
Given a list of integers, which denote a permutation.Find the previous permutation in ascending order.
Notice:The list may contains duplicate integers.
给定一个整数数组来表示排列，找出其上一个排列。
注意：排列中可能包含重复的整数
【题目链接】
【题目解析】
这题就是next permutation的逆过程。首先找到从后往前遍历，直到找到一个数（假设位置为i）比之它前一位数小（即该位到数组的最后是一个递增序列），然后将i到数组最后的所有数按递减排列。然后在这个递增数列里面找到第一个比i－1位置上数小的数，交换两个数的位置即可。如果i＝1则说明之前的整个数组都是递增序列，现在整个数组变为递减数列，正好是previous permutation，因此不用再做任何其他操作。
【参考答案】
评论
发表评论