algorithm - 下一个更大的偶数

Question

我们有一个数字 N，问题是找到最小的偶数 E，使得 E > N 并且 N 和 E 中的数字相同。 N 中的数字可能很大。

例如

1. 1 -> 34722641 答案是 34724126
2. 111 -> 没有偶数可能只是大于它。
3. 1123 -> 输出为 1132

我通过对数字的所有数字进行排列，用蛮力做到了这一点。我在想是否有更好的方法？有代码会更好。

谢谢。

Answer 1

您可以使用以下策略来寻找下一个排列:

假设您的number = 12344875要找到下一个更大的排列，你从右边开始，发现第一个数字小于前一个。在这种情况下:number = 12344875，这是 4。

现在您从 4 开始向右移动并找到那里的最小数字。即 5 -> 875。现在交换这 2 个数字，得到 12345874。

交换后，将 5 之后的数字按升序排序。 12345874 --> 12345784。这种策略总是会导致下一个更大的排列，只是这会同时给出偶数和奇数。

所以为了找到下一个偶数排列，你需要稍微改变一下。如果在最后一步中您有偶数，则将该部分排列直到偶数。

否则从右边重新开始。并找到第一个偶数，它的右边有一个更大的数字。例如，数字 = 123475531。现在与其右侧大于 4 的最小数字交换。导致以下 123575431.

由此将偶数 4 放在末尾并将数字放在中间交换的数字按升序排列，123575314 --> 123513574。

如果您有以下数字 136531。右边没有更大的偶数。所以你看下一个数字，看看右边是否有一个更大的数字(但不是第一个偶数)。这是 136531 --> 136531 所以交换它们并将偶数放在后面，最后按升序排列。 136531 --> 156331 --> 153316 --> 151336.

数字降序排列时无解(如97654)。

在进行此解释时，我意识到对于偶数，这会变得更加复杂。我稍后会尝试改进答案。

我希望这是有用的。干杯