是否有可能在一个列表中使用一次传递获得两个最大的数字?
本文关键字:两个 数字 列表 一个 有可能 一次 是否 | 更新日期: 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个元素。遍历数组,对于每一项:
- 如果列表尚未满,则插入 项
- 否则,如果项大于列表中最小的项,则插入该项并删除最小的项。
最后,列表将包含K个最大的元素,这正是我们想要的。
但是这个解决方案相当慢。使用自平衡二叉搜索树或跳跃表,你可以得到O(N log K)。(因为在一般情况下,排序不可能比O(N log N)更快,如果我们设置K = N,这种方法可以用于对整个数组进行排序,这看起来是我们能得到的最好结果。)
在K = 2的情况下,你不需要所有这些重型机械。只要两个变量表示列表中的两个位置就足够了。
是的。在遍历列表时,记录找到的最大数字,每当找到更大的数字时,在更新找到的最大数字之前,将找到的最大数字保存到第二大列表中。如果值大于第二大值,则更新第二大值