用于查找数组中最大和第二大数字的程序

Question

我已经在很多网站上搜索了这个问题.他们通过一些不同的方法来做到这一点.如果我将数组的第一个元素作为最大值输入,则此代码不提供输出a[0].我认为需要做一些小改动.有人可以告诉我吗？

#include <stdio.h>

int main() {
    int a[10], n;
    int largest1, largest2, i;

    printf("enter number of elements you want in array");
    scanf("%d", &n);
    printf("enter elements");
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    largest1 = a[0];
    for (i = 0; i < n; i++) {
        if (a[i] > largest1) {
            largest1 = a[i];
        }
    }
    largest2 = a[0];
    for (i = 1; i < n; i++) {
        if (a[i] > largest2 && a[i] < largest1)
            largest2 = a[i];
    }
    printf("First and second largest number is %d and %d ", largest1, largest2);
}

Answer 1

(我将忽略处理输入,它只会分散注意力.)

简单的方法是对它进行排序.

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

int cmp_int( const void *a, const void *b ) {
    return *(int*)a - *(int*)b;
}

int main() {
    int a[] = { 1, 5, 3, 2, 0, 5, 7, 6 };
    const int n = sizeof(a) / sizeof(a[0]);

    qsort(a, n, sizeof(a[0]), cmp_int);
    printf("%d %d\n", a[n-1], a[n-2]);
}

但这并不是最有效的,因为它是O(n log n),这意味着随着数组越大,比较的数量越快越大.不是太快,比指数慢,但我们可以做得更好.

我们可以用O(n)"线性时间"或"线性时间"来表示,随着数组越大,比较次数以相同的速率增长.

循环遍历跟踪最大值的数组,这是找到最大值的常用方法.当您找到新的最大值时,旧的最大值将成为第二高的数字.

而不是有第二个循环来找到第二高的数字,而是输入一个特殊情况,以便进入第二高的数字.

#include <stdio.h>
#include <limits.h>

int main() {
    int a[] = { 1, 5, 3, 2, 0, 5, 7, 6 };
    // This trick to get the size of an array only works on stack allocated arrays.
    const int n = sizeof(a) / sizeof(a[0]);

    // Initialize them to the smallest possible integer.
    // This avoids having to special case the first elements.
    int max = INT_MIN;
    int second_max = INT_MIN;

    for( int i = 0; i < n; i++ ) {
        // Is it the max?
        if( a[i] > max ) {
            // Make the old max the new 2nd max.
            second_max = max;
            // This is the new max.
            max = a[i];
        }
        // It's not the max, is it the 2nd max?
        else if( a[i] > second_max ) {
            second_max = a[i];
        }
    }

    printf("max: %d, second_max: %d\n", max, second_max);
}

可能有更优雅的方式来做,但最多只能进行2n次比较.充其量它会做n.

请注意,有一个未解决的问题{ 1, 2, 3, 3 }.应该返回3, 3还是2, 3？我会留给你决定并相应调整.