您可以这样输入O(n)
(n
位数是):
从右边开始,找到第一个数字对,以使左边的数字小于右边的数字。让我们用“ digit-x”来指代左数字。在数字-x的右边找到大于数字- x的最小数字,并将其放在数字-x的左侧。最后,将其余数字按升序排序-由于它们已经按 降序 排列,因此您要做的就是将它们反转(保存digit-x,可以将其放置在中的正确位置O(n)
)。
一个示例将使这一点更加清楚:
123456784987654321
以数字开头
123456784 987654321
^左数小于右数的从右到右的第一位
数字“ x”为4
123456784 987654321
^在右侧找到大于4的最小数字
123456785 4 98764321
^将其放在4的左侧
123456785 4 12346789
123456785123446789
^将数字右边的5排序。因为除
“ 4”已经按降序排列,我们要做的就是
颠倒顺序,找到正确的'4'位置
让我们用大写字母定义数字字符串,并用小写字母表示数字。语法的AB
含义是 “字符串A
和B
” 的串联。<
是字典顺序,当数字字符串长度相等时,它与整数顺序相同。
我们的原始数字N的形式为AxB
,其中x
是一位数字,并B
以降序排列。 我们的算法找到的数字是AyC
,其中y ∈ B
是最小数字> x
(由于x
选择的方式而必须存在,请参见上文),并且C
以升序排序。
假设有一些数字(使用相同的数字)N'
使得AxB < N' < AyC
。N'
必须以开头,A
否则它不能落在它们之间,因此我们可以将其编写为形式AzD
。现在我们的不等式是AxB < AzD < AyC
,它等于xB < zD < yC
三个数字字符串都包含相同数字的地方。
为了使这一点成为现实,我们必须有x <= z <= y
。由于y
是最小数字> x
,z
所以不能在它们之间,所以z = x
或z = y
。说z = x
。然后我们的不平等xB < xD < yC
,这意味着B < D
其中两个B
与D
具有相同的数字。然而,B是降序排序,所以是 没有字符串与比它大的数字。因此我们不能拥有B < D
。遵循相同的步骤,我们看到if z = y
不能拥有D < C
。
因此N'
不存在,这意味着我们的算法正确找到了下一个最大的数字。