4

正如标题所说，我必须找到数组中的第二大数字，如果该数组中的每个数字都相等，我应该写它是-∞。我写了这个，有人可以检查一下我是否可以更好地优化它吗？这个数组只是一个例子，它应该是 x[1...n] 但因为我必须将它重写为伪代码，所以我以那个为例

#include <stdio.h>
int main()
{
    int x[7]={90,90,78,41,21,27,35};
    int i, max, secmax, y;
    secmax=0;
    max=x[0];
    for(i=1;i<=7;i++)
        {
        if (x[i]>max)
            {
            secmax=max;
            max=x[i];
            }
        else if (x[i]>secmax&&x[i]<max)
                {
            secmax=x[i];
            }
        }

    for(i=0;i<7;i++)
        if(x[i]==x[i+1])
            y++;

    if (y==6)
        printf("sec max to minus nieskonczonosc \n");
    else 
        printf("max to %d a secmax to %d\n",max,secmax);
    return 0;
}
4

3 回答 3

3

secmax您可以通过最初设置为负无穷大来避免对整个数组进行最后一次扫描。这样，它将始终具有正确的值。

此外，您的代码中有一个错误：i<=7应该替换为i < sizeof(x)/sizeof(x[0]). 否则你x[i]会给你一个段错误。

于 2013-10-17T22:53:00.077 回答
3

这是您可以执行的操作：

int get_second_max(int *x, size_t n)
{
    int max[2] = {-MAX_INT,-MAX_INT};
    int i = 0, same = 1;
    if (NULL == x || 0 == n)
        return -MAX_INT;

    max[0] = x[0];
    max[1] = x[0];
    for(i = 1; i < n; i++) {
        /* same is used to check 
         * if the array contains 
         * the same number all along.
         */
        same &= (x[i] == x[i-1]);
        /* At the i-th iteration :
         * -> max[0] stores the maximum value
         * -> max[1] stores the second maximum value
         */

        /* We hit a new max value, we must :
         * 1. Update the second max value with the current max value
         * 2. Update the current max value with the new max we found
         */
        if(x[i] > max[0]) {
            max[1] = max[0];
            max[0] = x[i];
        } else if(x[i] > max[1]) {
            max[1] = x[i];
        }
    }
    if(same) {
        return -MAX_INT;
    } else {
        return max[1];
    }
}
于 2013-10-17T23:00:16.480 回答
0

我做了一些更改并添加了一些评论。代码下方讨论。

#include <limits.h> // for INT_MIN macro
#include <stdio.h>
int main()
{
    // Let the compiler count length of array.
    // -- declare "x[]", no need to specify length
    const int x[] = { 90, 90, 78, 41, 21, 27, 35 };
    // -- use sizeof() math to find length of array
    // -- use const int rather than #define so debugger can see value
    const int len = sizeof(x) / sizeof(x[0]);
    int i, max, secmax, same_count;

    if (0 == len)
    {
        // zero-length list: return INT_MIN
        printf("sec max to minus nieskonczonosc: %d\n", INT_MIN);
        return 0;
    }

    secmax = max = INT_MIN;

    same_count = 0;

    // start loop at 0
    for(i = 0; i < len; ++i)
        {
        // We'll use the same idea you originally used to find if all values were
        // the same, but do it as part of the same loop.  No need to loop over
        // the values twice.  For a short list, looping twice is not a big deal,
        // but for really large data sets it will save lots of time to do it this way.
        same_count += (x[0] == x[i]);

        if (x[i]>max)
            {
            // Found value greater than current max; shift max down to secmax
            // and save new max value.
            secmax=max;
            max=x[i];
            }
        else if (x[i]>secmax && x[i]<max)
            {
            // It wasn't greater than max, but is greater than secmax.
            // Save new secmax value.
            secmax=x[i];
            }
        }

    if (len == same_count)
        printf("sec max to minus nieskonczonosc: %d\n", INT_MIN);
    else 
        printf("max to %d a secmax to %d\n",max,secmax);

    return 0;
}

我们无能为力来改善运行时间。您的代码已经在做简单的事情来找到所需的值。

我们可以做的一件事是通过在第一个循环内完成它的工作来摆脱你的第二个循环。

@Rerito 的回答改变了算法：不是计算有多少值是相同的，而是查看计数是否与长度匹配，而是从位开始，1并使用按位“和”进行值比较。如果比较失败，比较的结果将为零，并且值为 0 的按位“与”结果为 0。因此，如果比较失败，则初始 1 位被清除为 0 位，当循环结束，如果那个 1 位仍然设置，那么每个值必须是相同的。

我保留了计算有多少值相同的基本算法，然后检查计数是否与长度匹配。我重命名了计数变量，因为该名称y没有提供信息，我将计数更新移动到第一个循环内（然后摆脱了第二个循环），我重新编写了代码，以便您可以更改数组值，它应该只是工作。

在代码中散布未连接的“魔术”值是一种不好的做法。您的原始代码7在三个位置具有 a 和6... 因此当有人更改数组的长度时，它会为错误打开。我的代码让 C 编译器计算数组中有多少值，设置一个常量 ( len)，然后专门使用该常量。因此，您可以简单地在数组中添加或删除值，并且更改后的代码仍然可以正常工作。

编辑：@sds 写道：“您可以通过将 secmax 最初设置为负无穷大来避免对整个数组的最后一次扫描。这样它总是有正确的值。”

哦，哇，他是对的！如果每个值都相同，我们所要做的就是设置secmax我们想要返回的值，因为代码只secmax在代码看到一个小于的值时才被写入 set max，如果每个值都相同，那么secmax将从不改变。

于 2013-10-18T01:34:37.470 回答