查找整数列表中倒数第二个最大的元素 C#

Question

我有一个

list<int> input = //from db of one million records

100万条记录。

虽然我知道使用input.OrderByDescending().Skip(1).Take(1)可以解决问题，但是如果我有100万条记录，使用OrderBY不是最佳做法。

在这种情况下，当我们有更多记录时，哪种解决方案是最好的？

Answer 1

在跟踪max以及max2时扫描列表，您将获得O(N)与O(N * log(N))的时间复杂度：

// Maximum value
int max  = Math.Max(input[input.Count - 1], input[input.Count - 2]);
// Second greatest   
int max2 = Math.Min(input[input.Count - 1], input[input.Count - 2]);
// i >= 0: Comparing with 0 is slightly faster then with Count
for (int i = input.Count - 3; i >= 0; --i) {
int v = input[i];
if (v >= max) {
max2 = max;
max = v; 
}
else if (v > max2) 
max2 = v;
}

编辑：如果应该忽略重复项(请参阅下面的评论)，因此[1, 2, 3, 4, 4, 4, 4]的答案应该是3，而不是4：

// Maximum value
int max = int.MinValue;
// Second greatest   
int max2 = int.MinValue;
// i >= 0: Comparing with 0 is slightly faster then with Count
for (int i = input.Count - 1; i >= 0; --i) {
int v = input[i];
if (v > max) {
max2 = max;
max = v;
}
else if (v > max2 && v != max)
max2 = v;
}

Answer 2

如果列表仅包含不同的值，则还可以执行以下操作：

var max = input.Max();
input.Remove(max);
var result = input.Max();

Answer 3

您可以通过跟踪下一个最大值并遍历列表一次来做到这一点。

int max = Int32.MinValue;
int nextMax = Int32.MinValue;
for(int i=0; i<list.Count(); i++)
{
if(list[i] > max)
{
nextMax = max;
max = list[i]; 
}
else if(list[i] > nextMax)
{
nextMax = list[i];
}
}

Answer 4

这是一个仅迭代一次并使用 LINQ 和 C# 7 元组的解决方案：

var input = Enumerable.Range(0, 101);
var topTwo = input.Aggregate((Biggest: Int32.MinValue, SecondBiggest: Int32.MinValue),
(acc, next) =>
{
if (next > acc.Biggest)
{
acc.SecondBiggest = acc.Biggest;
acc.Biggest = next;
}
if (next < acc.Biggest && next > acc.SecondBiggest)   
acc.SecondBiggest = next;
return acc;
});
WriteLine(topTwo.SecondBiggest);  // 99