C#实现查找数组中第二大元素的方法及代码示例

我近期在学习数据结构与算法（DSA）提升编程逻辑能力，最初用C#实现数组第二大元素查找功能时一直调试失败，后来梳理出一套逻辑非常直白的实现方式，对编程新手来说理解门槛极低，完整可运行代码如下：

int[] arr = new int[8];
int secondlarge;
int temp;
// 读取用户输入填充数组
for (int i = 0; i < arr.Length; i++)
{
    Console.Write("Index - {0} :", i);
    arr[i] = Convert.ToInt32(Console.ReadLine());
}

Console.WriteLine("Elements in array are: ");
for (int i = 0; i < arr.Length; i++)
{
    Console.Write("{0} ", arr[i]);
}
Console.WriteLine();

// 第一次遍历找数组最大值
temp = arr[0];
for (int i = 0; i < arr.Length; i++)
{
    if (arr[i] > temp)
    {
        temp = arr[i];
    }
}

// 第二次遍历跳过最大值，找剩余元素里的最大值即为第二大
secondlarge = arr[0];
for (int i = 0; i < arr.Length; i++)
{
    if (temp == arr[i])
    {
        continue;
    }
    if (arr[i] > secondlarge)
    {
        secondlarge = arr[i];
    }
}

Console.WriteLine("Second Largest Number is : " + secondlarge);

实现逻辑拆解 #

整个实现没有用到任何复杂API或技巧，逻辑完全线性：

• 先初始化长度为8的整型数组，逐行读取控制台输入填充数组，打印全部元素方便核对输入是否正确
• 第一轮遍历全数组，记录数组中的最大值
• 第二轮遍历全数组，跳过所有和最大值相等的元素，在剩余元素中找到的最大值就是第二大值
• 最终打印输出第二大值的结果

补充说明 #

• 这个实现的时间复杂度为O(n)，总共仅遍历2次数组，不管是新手练习还是日常业务场景使用，效率都完全足够
• 现有代码没有处理「数组内所有元素值完全相同」的边界场景，这种情况下返回的第二大值会和最大值相等，实际使用时可以根据需求加一层判断做特殊处理
• 如果追求更少的遍历次数，可以优化为单次遍历同时维护最大值、第二大值两个变量，但对新手来说，先把这种拆分步骤的直白写法写对、把逻辑理清楚，比一开始就追求极简写法的学习效果好很多

内容的提问来源于stack exchange，提问作者Rao Ahmed