是否有可能在一个列表中使用一次传递获得两个最大的数字?

本文关键字:两个 数字 列表 一个 有可能 一次 是否 | 更新日期: 2023-09-27 18:11:48

是否有可能在数组中找到2个最大的数字,并且只通过集合循环一次?

我在面试中遇到了这个问题,但没有及时回答。

是否有可能在一个列表中使用一次传递获得两个最大的数字?

看起来很简单…

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
  • 否则if必须小于,但如果大于second-maximum,则为max2赋新值

一般来说,你可以在一个数组中找到K个最大(或最小)的数字,对任何K使用一次遍历。总时间复杂度将是O(NK),其中N是数组的大小:

保留一个排序过的数字列表,其中最多有K个元素。遍历数组,对于每一项:

  1. 如果列表尚未满,则插入
  2. 否则,如果项大于列表中最小的项,则插入该项并删除最小的项。

最后,列表将包含K个最大的元素,这正是我们想要的。

但是这个解决方案相当慢。使用自平衡二叉搜索树或跳跃表,你可以得到O(N log K)。(因为在一般情况下,排序不可能比O(N log N)更快,如果我们设置K = N,这种方法可以用于对整个数组进行排序,这看起来是我们能得到的最好结果。)

在K = 2的情况下,你不需要所有这些重型机械。只要两个变量表示列表中的两个位置就足够了。

是的。在遍历列表时,记录找到的最大数字,每当找到更大的数字时,在更新找到的最大数字之前,将找到的最大数字保存到第二大列表中。如果值大于第二大值,则更新第二大值