c# - 查找整数列表中倒数第二大的元素 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;
  }