How to return sum of two highest value in List<int> in most efficient way? C#-CodePudding

I'm trying to pass a pre-written test with focus on performance. What is the most efficient way to return the sum of the two highest numbers in a List of int? I have tried the following and according to the test it wasn't fast enough when it comes to larger lists:

1.  list.Sort();
    list.Reverse();
    return list[0]   list[1];

2.  return list.OrderByDescending(num => num).FirstOrDefault()   list.OrderByDescending(num => num).Skip(1).FirstOrDefault();

3.  var secondHighest = list.Distinct()
                            .OrderByDescending(i => i)
                            .Skip(1)
                            .First();

    return list.Max()   secondHighest;

CodePudding user response：

Any sorting operation would be O(n log n) (OrderByDescending, Sort) at best (on random data) though current task is achievable in O (n) with simple loop:

var first = int.MinValue;
var second = int.MinValue;
foreach(var i in list)
{
    if(i > first)
    {
        second = first;
        first = i;
    }
    else if(i > second)
    {
        second = i;
    }
}

var result = first   second;

CodePudding user response：

Another alternative:

return list.OrderByDescending(num => num)
    .Take(2)
    .Sum();

CodePudding user response：

Well, I'm proposing this algorithm:

highest = 0
highestSet = false
secondHighest = 0
secondHighestSet = false
foreach item in list
    if item >= highest or !highestSet
        if highestSet
          secondHighest = highest
        highestSet = true
        highest = item
    else if item >= secondHighest or !secondHighestSet
        secondHighestSet = true
        secondHighest = item

return highest   secondHighest

Input set of [3, 2, 3, 2] will return 6. This is O(n) time complexity.