如何返回列表中的两个最高价值的总和。以最有效的方式？ C＃

Question

我正在尝试通过侧重于性能的预先编写的测试。返回INT列表中两个最高数字总和的最有效方法是什么？我尝试了以下操作，根据测试，在较大列表方面还不够快：

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;

Answer 1

任何直接的排序操作都将是o（n*log（n））（orderby（discending），sort> sort）最好（在随机数据上），尽管当前任务是可以在o（n）带有简单循环（假设列表中至少有2个项目，对于有2个或更少元素的情况，只需返回list.sum.sum.sum（））

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;

：值得注意的是可以在某些情况下，以Orderby（discending）与first（ordefault）或可能的进行进行 toge toke （请参阅）（请参阅（请参阅）（请参阅） a href =“ https://github.com/dotnet/corefx/pull/2401” rel =“ nofollow noreferrer”>一个， 两个，，

Answer 2

好吧，我建议使用此算法：

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

[3,2,3,2]的输入集，它将返回6。这是O（n）时间复杂性。

对于一组[3]，它将返回3。

Answer 3

LINQ可以是一个很好的解决方案。

long sum = 0;
if(list.Count > 1) 
  sum = list.OrderByDescending(z=>z).Take(2).Sum();
else
  sum = list.Sum();

Answer 4

您可以尝试这种简单的方法：

list.Sort();
list.Reverse();
var secondHighest=list.Take(2).Sum();
 
return secondHighest;

或者

 list=list.OrderByDescending(o=>o).ToList();
 var secondHighest=list.Take(2).Sum();
 
return secondHighest;

首先，它对您的列表进行排序，然后将其倒转，现在您已经进行了降序的列表，而不是采用2个最高元素并汇总它们。