找到复杂度最小的数组中的第二个最大数字

Question

试图用Google搜索,但没有运气.如何在复杂度最小的阵列中找到第二个最大数字？

代码或想法将有很大帮助.

我可以遍历一个数组并查找之后的最大数,我有最大数,然后再次循环数组,以相同的方式找到第二个数.

但可以肯定的是效率不高.

Answer 1

您可以对数组进行排序并在第二个索引处选择项目,但是下面的O(n)循环会快得多.

int[] myArray = new int[] { 0, 1, 2, 3, 13, 8, 5 };
int largest = int.MinValue;
int second = int.MinValue;
foreach (int i in myArray)
{
 if (i > largest)
 {
  second = largest;
  largest = i;
 }
else if (i > second)
    second = i;
}

System.Console.WriteLine(second);

要么

试试这个(使用LINQ):

int secondHighest = (from number in test
                             orderby number descending
                             select number).Distinct().Skip(1).First()

如何在Visual C#中获得数组中第二高的数字？