c - 这是一个 C 程序，用于查找具有相同数字的下一个最大数字。但是没有通过一个测试用例

Question

这是一个 C 程序，用于查找具有相同数字的下一个更大的数字。该程序适用于除一个以外的所有给定测试用例。当输入为 472 时，预期输出为 724。但我的输出是 247。谁能帮我找出错误？

我试图解决这个问题的逻辑是:

1. 从最右边的数字开始遍历给定的数字，一直遍历直到找到比之前遍历的数字小的数字。例如，如果输入数字是 534976，我们在 4 处停止，因为 4 小于下一个数字 9 .如果我们找不到这样的数字，则输出为 Not Possible。

2. 现在在上面找到的数字“d”的右侧搜索大于“d”的最小数字。对于 534976，4 的右侧包含 976。大于 4 的最小数字是 6。

3. 交换上面找到的两个数字，我们得到上面例子中的536974。

4. 现在对从“d”旁边的位置到数字末尾的所有数字进行排序。排序后得到的数字就是输出。对于上面的例子，我们将数字排序为粗体 536974。我们得到 536479，这是输入 534976 的下一个更大的数字。

这是我的代码:

#include <stdio.h>
#include <stdlib.h>

int main() {
    int N, dig[100], i = 0,j, temp, t, s, k, l, min, temp1;

    scanf("%d", &N);
    while (N > 0) {
        dig[i] = N % 10;
        i++;
        N = N / 10;
    }

    for (j = 0; j <= i; j++) {
        if (dig[j] > dig[j + 1]) {
            s = j;
            break;
        }
    }

    min = dig[s];
    //printf("%d ", min);
    for (k = s; k >= 0; k--) {
        if (dig[k] <= min) {
            min = dig[k];
            t = k;
        }
    }
    //printf("%d ", t);
    temp = dig[t];
    dig[t] = dig[s + 1];
    dig[s + 1] = temp;
    for (k = 0; k <= s; k++) {
        for (l = k + 1; l <= s; l++) {
            if (dig[k] < dig[l]) {
                temp1 = dig[k];
                dig[k] = dig[l];
                dig[l] = temp1;
            }
        }
    }
    for (k = i - 1; k >= 0; k--) {
        printf("%d", dig[k]);
    }
}

Answer 1

您的算法似乎是正确的，但循环不正确。一些索引边界相差一个，与 <= 的比较不正确。通过增加 10 的幂来存储数字，虽然更实用是违反直觉的，并且使算法到代码的转换变得复杂。

这是一个更正后的版本，它输出所有更大的数字。您可以通过管道轻松检查输出 sort -c验证订单和wc -l验证是否已找到所有组合(对于具有 n 位的数字，最多应有 n! - 1 个更大的数字)。

#include <stdio.h>

int main() {
    int N, dig[100], i, j, s, t, k, l, temp;

    if (scanf("%d", &N) != 1 || N < 0)
        return 1;

    for (;;) {
        for (i = j = 100; N > 0;) {
            dig[--i] = N % 10;
            N = N / 10;
        }
        for (s = j - 2; s >= i; s--) {
            if (dig[s] < dig[s + 1]) {
                break;
            }
        }
        if (s < i) {
            /* no greater number with the same digits */
            break;
        }
        t = s + 1;
        for (k = t + 1; k < j; k++) {
            if (dig[k] < dig[t] && dig[k] > dig[s]) {
                t = k;
            }
        }
        temp = dig[t];
        dig[t] = dig[s];
        dig[s] = temp;
        for (k = s + 1; k < j; k++) {
            for (l = k + 1; l < j; l++) {
                if (dig[k] > dig[l]) {
                    temp = dig[k];
                    dig[k] = dig[l];
                    dig[l] = temp;
                }
            }
        }
        N = 0;
        for (k = i; k < j; k++) {
            N = N * 10 + dig[k];
            printf("%d", dig[k]);
        }
        printf("\n");
    }
    return 0;
}

输入:472

输出:

724
742