在一个数组中查找第二大的数字（C语言）

Question

正如标题所述，我必须在一个数组中找到第二大的数字，如果该数组中的每个数字都相等，则应写为-∞。我写了这个，请问有人能检查一下是否可以更好地进行优化吗？ 这个数组只是一个例子，实际应为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;
}

- deviance

Answer 1

以下是您可以做的事情：

以下是您可以做的事情：

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];
    }
}

- Rerito

---

假设数组为 { 5, 1, 2, 3, 4 } — max[1] 会在什么时候被设置为 4？ - r3mainer

我在循环中忘记了一个子句，现在应该已经正确了。感谢您指出这个问题 :) - Rerito

假设数组是 { 99, 99, 99, 8 } ... 那么这段代码不会将 secmax 设为 99 吗？这就是为什么原始代码有 &&x[i]<max 子句的原因，这也是我在答案中加入的。 - steveha

Answer 2

你可以通过将 secmax 最初设置为负无穷来避免对整个数组的最后一次扫描。这样它总是会有正确的值。

另外，你的代码中存在一个 bug: i<=7 应该替换为 i < sizeof(x)/sizeof(x[0])。否则你的 x[i] 会导致段错误。

- sds

---

对于 secmax 的深刻观察点赞。在我看来，第二句话写得不太清楚，但我同意基本观点（请参见我的示例代码，我使用 sizeof() 技术设置了一个常量 len）。 - steveha

Answer 3

我做了一些更改并添加了一些注释。代码下面有讨论。

#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和一个6，因此当有人更改数组的长度时，它容易出现错误。我的代码让C编译器计算数组中有多少个值，设置一个常量（len），然后专门使用该常量。因此，您可以简单地添加或删除数组中的值，而更改后的代码仍然可以正确工作。

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

哇，他说得对！我们所要做的就是将secmax设置为我们希望返回的值，如果每个值都相同，因为代码只在看到小于max的值时才设置secmax，如果每个值都相同，则secmax永远不会改变。

- steveha

---

非常感谢 :) 我对编程非常新，所以这真的很有帮助。关于那些随机值 - 就像我说的，这只是一个示例数组，因为我必须将其重写为伪代码，并且在那里它将是x [n]。最初我用C语言编写它，因为我正在学习它。 - deviance

请注意，虽然我有很多积分，所以并不是非常需要更多的积分，但在StackOverflow上给你认为有帮助的答案点个赞是好习惯，并且要“接受”你得到的最有帮助的答案。 - steveha

Answer 4

In my code I am replacing the largest number to zero in the array after printing it, this way we have removed the largest. Then using the new array to find the second largest number. This code is beginner friendly and easy to understand  
// Program to print second largest number
#include<stdio.h>
int main()
{
    int num[10],n,i,largest,second;
    printf("Enter n: ");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        printf("Enter num %d: ",i+1);
        scanf("%d",&num[i]);
    }
    largest = num[0];
    for(i=1;i<n;i++)
    {
        if(largest<num[i])
         largest = num[i];
    }
    printf("The largest is %d\n",largest);
    for(i=0;i<n;i++)
    {
        if(largest == num[i])
        {
            num[i] = 0;
        }
    }
    printf("Array is: \n");
    for(i=0;i<n;i++)
    {
                                                                                                        printf("%d\t",num[i]);
    }
    second = num[0];
    for(i=1;i<n;i++)
    {
        if(second<num[i])
          second = num[i];
 
    }
    printf("The second largest is %d",second);
    return 0;
}

- Sejal Rawat

---

根据目前的写法，你的回答不够清晰。请编辑以添加更多细节，帮助其他人理解这如何回答所提出的问题。你可以在帮助中心找到关于如何撰写好回答的更多信息。 - undefined