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

本文关键字：两个 数字 列表 一个 有可能 一次 是否 | 更新日期: 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. 项
  2. 否则，如果项大于列表中最小的项，则插入该项并删除最小的项。

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

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

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

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

相关文章：