是否可以使用单次传递获得列表中的2个最大数字？

Question

是否有可能在数组中找到2个最大的数字,并且只能循环遍历该集合一次？

我把这作为一个面试问题并没有及时得到它.

Answer 1

看起来很简单..

int[] nums = { 3, 1, 4, 1, 5, 9, 2, 6 };

int max1 = -1;
int max2 = -1;
foreach (int num in nums)
{
  if (num > max1) { max2 = max1; max1 = num; }
  else if (num > max2) { max2 = num; }
}    

例如:

// 3: max2 = -1; max1 = 3;
// 1: max2 = 1;
// 4: max2 = 3; max1 = 4;

快速解释:

• 将-1定义为占位符,可以使用int.MinValue,或者更好的是单独的bool来表示不匹配
• 如果测试的值大于当前最大值(max1),则将当前最大值分配给max2,将新值分配给max1
• 否则,如果必须更小,但如果它大于第二个最大值,则为max2分配新值