在整数列表C＃中找到倒数第二个最大元素

Question

我有一个list<int> input = //from db of one million records的百万记录。尽管我知道使用input.OrderByDescending().Skip(1).Take(1)可以解决问题，但是如果我有一百万条记录，则不是最佳做法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

您可以通过跟踪下一个最大值并在列表中进行一次迭代来做到这一点。

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 3

这是一个仅使用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