【字典序】
Problem Link
给你一个正整数的数组 A
(其中的元素不一定完全不同),请你返回可在 一次交换(交换两数字 A[i]
和 A[j]
的位置)后得到的、按字典序排列小于 A
的最大可能排列。
如果无法这么操作,就请返回原数组。
Example:
示例 1:
输入:[3,2,1]
输出:[3,1,2]
解释:
交换 2 和 1
示例 2:
输入:[1,1,5]
输出:[1,1,5]
解释:
这已经是最小排列
示例 3:
输入:[1,9,4,6,7]
输出:[1,7,4,6,9]
解释:
交换 9 和 7
示例 4:
输入:[3,1,1,3]
输出:[1,3,1,3]
解释:
交换 1 和 3
提示:
1 <= A.length <= 10000
1 <= A[i] <= 10000
Analysis
这道题目的关键是 按字典序排列小于 A 的最大可能排列
, 那么有
对当前序列进行逆序查找,找到第一个降序的位置i
,使得$A[i]>A[i+1]$
- 由于$A[i]>A[i+1]$,必能构造比当前字典序小的序列
- 由于逆序查找,交换
A[i]
为最优解
寻找在 A[i]
最左边且小于 A[i]
的最大的数字 A[j]
- 由于 $A[j] < A[]i]$, 交换
A[i]
与A[j]
后的序列字典序一定小于当前字典序 - 由于
A[j]
是满足关系的最大的最左的,因此一定是满足小于关系的交换后字典序最大的
这里的两条,最大和最左边缺一不可,可以结合样例
[3, 1, 1, 3] => [1, 3, 1, 3]
[3, 1, 2, 3] => [2, 1, 3, 3]
[4, 1, 2, 3] => [3, 1, 2, 4]
理解
Solution 【字典序】 ( 1ms)
执行用时 : 1 ms, 在Previous Permutation With One Swap的Java提交中击败了90.41% 的用户
内存消耗 : 50.9 MB, 在Previous Permutation With One Swap的Java提交中击败了100.00% 的用户
|
|
复杂度分析
时间:$O(N)$
空间:$O(1)$