查找数组中第二大元素而不进行排序

Question

我知道将两个变量初始化为 的单一遍历方法INT_MIN。但我的问题是为什么我们要初始化两个变量INT_MIN以及这里的目的是什么INT_MIN？

为什么我们不能像我在下面的代码中所做的那样将两个变量初始化为其第一个元素？因为当我手动检查代码时，没有发现任何错误。那么为什么代码不能正常运行呢？

#include <stdio.h>

int main(void) {
    int x[10];
    int i, n;
    int first = x[0];
    int second = x[0];

    printf("Input the size of array :");
    scanf("%d", &n);

    printf("Input %d elements in the array :\n", n);
    for (i = 0; i < n; i++) {
        printf("x[%d]: ", i);
        scanf("%d", &x[i]);
    }

    for (i = 0; i < n; ++i) {
        if (first < x[i]) {
            second = first;
            first = x[i];
        } else
        if (x[i] > second && x[i] != first) {
            second = x[i];
        }
    }

    if (second == first)
        printf("There is no second largest element\n");
    else
        printf("\nThe Second largest element in the array is: %d", second);

    return 0;
}

Answer 1

您的代码存在几个问题：

• 该数组的x长度定义为10，但在将first和设置second为其第一个元素的值时未初始化。
• 您没有测试 的返回值scanf()，导致输入失败时出现未定义的行为。
• 在将值读入 之前，您不测试n是否 小于或等于。10x
• 您需要特殊情况n <= 0，因为不会读取任何值x。

这是修改后的版本：

#include <stdio.h>

int main(void) {
    int x[10];
    int i, n, first, second;

    printf("Input the size of array :");
    if (scanf("%d", &n) != 1 || n < 0 || n > 10) {
        printf("invalid input\n");
        return 1;
    }

    if (n <= 0) {
        first = second = 0;
    } else {    
        printf("Input %d elements in the array:\n", n);
        for (i = 0; i < n; i++) {
            printf("x[%d]: ", i);
            if (scanf("%d", &x[i]) != 1) {
                printf("invalid input\n");
                return 1;
            }
        }
        first = second = x[0];
        for (i = 1; i < n; ++i) {
            if (first < x[i]) {
                second = first;
                first = x[i];
            } else
            if (x[i] > second && x[i] != first) {
                second = x[i];
            }
        }
    }

    if (second == first)
        printf("There is no second largest element\n");
    else
        printf("\nThe Second largest element in the array is: %d\n", second);

    return 0;
}

关于另一种实现，其中first和second被初始化为INT_MIN并且循环从 开始i = 0，技巧是INT_MIN最小的可能int值，因此first将<=与数组的所有值进行比较，因此不会隐藏较小的值。对于在传递空数组时查找数组中的最大值的函数来说，它也是一个很好的默认返回值。

对于您的案例研究，该INT_MIN方法不起作用，算法将在具有单个重复值的数组上失败：在扫描结束时，first将设置为该值并且second仍然为INT_MIN。

• 测试first == second将产生等于 的第二最大值INT_MIN，这是不正确的。
• 确定所有值是否相同的测试second == INT_MIN也是不正确的，因为具有值的数组{ 1, INT_MIN }确实具有等于 的第二最大值INT_MIN。

您的方法可以正常工作，而替代方案则需要以不同的方式编写，并使用额外的变量。事实上，这篇文章中提出的解决方案是错误的，这个、这个、这个以及互联网上无数的随机代码也是错误的。