实现下一个排列,它将数字重新排列为大小为 N 的给定数组 A 的数字下一个更大的排列。
如果无法进行这种排列,则必须将其重新排列为尽可能低的顺序,即按升序排序。
此问题的测试用例包括:
输入:A = [20, 50, 113]
输出:[20, 113, 50]
[20, 113, 50]
如何大于[20, 50, 113]
?
同样地 输入:A = [5, 18, 9]
输出:[9, 5, 18]
下一个排列而不是[5,9,18]
如何?
怎么大于 [20, 50, 113]?
因为它在字典上大于,所以其工作原理如下:
如果第一项大于或小于,则这就是结果。
否则,如果它们相等,那么如果第二项大于或小于,那么这就是结果。
否则,如果它们相等,那么如果第三项大于或小于,那么这就是结果。
否则它们是平等的。
所以[20, 113, 50] > [20, 50, 113]
因为在步骤 1:20 == 20
和步骤 2:113 > 50
.
同样:[5, 9, 18] < [5, 18, 9]
因为9 < 18
,[9, 5, 18] > [5, 18, 9]
因为9 > 5
。
怎么大于 [20, 50, 113]?
在
[20, 50, 113]
中,最后一个递增的 length-2 区间是[50, 113]
,然后我们从右到左选取[113, 113]
中的第一个元素(方程到[113]
),使其大于50
。用50
交换,然后反转间隔(50, 113]
,这样会给你[20, 113, 50]
。输出 :
[9, 5, 18]
下一个排列而不是 [5,9,18] 如何?从
A = [5, 18, 9]
找到[5, 18]
,
从找到[18, 9]
9
,
交换(5
,9
) 得到[9, 18, 5]
,
反向([18, 5]
) 得到[5, 18]
,
所以你得到:[9, 5, 18]
.
下一个排列表示下一个最大的数字
例如 如果一个数组是 arr = {1, 2, 3, 6, 5, 4}
那么这个数字就123654
它的下一个更大的元素是124356;
所以返回数组 {1, 2, 4, 3, 5, 6}。