data-structures - 查找给定数字的下一个较大的字谜

Question

找到给定数字的下一个较大字谜的有效算法是什么？

例子：

1. 输入：7813 -> 输出：7831
2. 输入：3791 -> 输出：3917
3. 输入：4321 -> 输出：（无）

Answer 1

基本上你从右到左移动数字。一旦你找到一个递减的数字，你就停下来。将该数字与之前的所有数字进行比较。将其替换为下一个最高数字，然后按升序对其余数字进行排序。例如：

取 978654321。 1) 从右向左移动，直到你得到一个递减的数字：

Stop at the 7 because that is the first digit that decreases.

2）找到我们已经看到的下一个最大的数字：

out of 1 2 3 4 5 6 and 8, 8 is the next largest digit to 7.

3）按升序对剩余数字进行排序并将其附加到末尾。

1234567

产生 981234567

复杂：

n 是位数。

步骤 1) O(n) 因为在最坏的情况下，数字会增加（或保持不变）直到最后一位数字。

步骤 2) O(n) 因为在最坏的情况下，您必须将该数字与所有 n 位数字进行比较。

步骤 3) O(n lg n) 因为你必须排序，最好的排序算法是 nlgn。

所以这个算法在 O(n lg n) 中运行。再次，其中 n 是数字中的位数。