下一个更大的偶数

Question

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

例如

1 -> 34722641 答案为 34724126
111 -> 没有偶数可能只是大于它。
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）无解。

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

我希望这有用。干杯

Answer 2

找到最右边的数字 i，它的右边有一个更高的数字 j，其中 j 不是右边最高的偶数，e。选择最小的 j，切换 i 和 j，将 e 放在最右边，然后将 [=10= 右边的数字排序（升序） ] 是（不包括 e）。

Answer 3

找到给定数字的下一个更大的数字。例如 - 对于 1234，下一个更大的数字是 1243，对于 534976，下一个更大的数字是 536479。可以找到算法here.如果最后一位是偶数那么你已经找到了下一个更大的偶数。
否则，重复上述步骤，直到找到偶数number.ie-找到下一个更大的偶数数字比现在新的输入数字作为那个我们在上一步输出（即使我们没有找到想要的输出(大于偶数))

例如 - 输入数字 - 21856521，运行第一步产生 - 21861255（奇数）所以我们再次运行 21861255 的第 1 步产生 21861525（再次奇数），运行ning 再次产生 21861552

PS：C++ 代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main(){
    string s;cin>>s;
    int n = s.length();
    while(true){
        int idx = -1;
        for(int i=n-2;i>=0;--i){
            if(s[i]<s[i+1]){
                idx = i;
                break;
            }
        }
        if(idx==-1){
            cout<<-1<<endl;
            break;
        }
        int swapidx = -1;
        for(int i=n-1;i>=idx+1;--i){
            if(s[i]>s[idx]){
                swapidx = i;
                break;
            }
        }
        swap(s[idx],s[swapidx]);

        //swapidx will never remain -1 bcz. we will surely find an element greater than s[idx](the right next element to idx is greater than s[idx])


        sort(s.begin()+idx+1,s.end());

        if((s[n-1]-'0')%2==0){
            cout<<s<<endl;
            break;
        }
    }
    return 0;
}

下一个更大的偶数

Next Greater Even Number

algorithm

stl-algorithm