Find the second maximum number in an array with the smallest complexity

Question

Tried to googled it but with no luck. How can I find the second maximum number in an array with the smallest complexity?

code OR idea will be much help.

I can loop through an array and look for the maximum number after that, I have the maximum number and then loop the array again to find the second the same way.

But for sure it is not efficient.

Answer 1

You could sort the array and choose the item at the second index, but the following O(n) loop will be much faster.

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);

OR

Try this (using LINQ):

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

How to get the second highest number in an array in Visual C#?