我进行了这项练习，无法弄清自己所缺少的内容。它实际上与现有问题非常相似，但是不一样，解决方案也可能不一样。存在的问题：从一组范围中查找最频繁的数字-
问题：
在[0，n d ]的范围内给您n个范围[a i，b i ]，其中d是一个恒定的正整数。a i，b i也是整数，并且每个i（i = 1，...，n）为0 <= a i <= b i <= n d。
编写算法以查找出现在最大范围[a i，b i ]中的整数z 。复杂度必须是线性的（作为n，d的函数）。
在我看来，这是一个经典的计数/基数排序问题：使用k = n作为基数，排序的复杂度变为O（d * n）。问题是，下一步该怎么做？我对此有些困惑。在相关问题中，有一个假设是范围只能是某个大小，而在我的问题中没有这样的假设，并且理论上可以有[0，n d ]的范围，介于两者之间。
随机示例：
输入：[1、3]，[5、10]，[5、11]，[6、17]，[8、9]，[9、21]，[11、15]，[12、12] 输出：9
排序是个好主意（基数排序似乎是一种方法），但是我不会对间隔进行排序。相反，我将使用扫掠线样式方法。想象一下从0到n ^ d的数字线上绘制的间隔。现在我们从左向右“扫动”。
有趣的一点是，与当前位置相交的间隔可以改变的情况是间隔的起点/终点。请注意，我们总是可以选择起点或终点之一作为解决方案。
因此，我们只考虑这些点并从左向右扫描：
events = start points UNION end points
sort events (rank start points before end points in case of a tie)
count = 0
max = 0
for each event x in sorted order
if x is start point
count++
if x is end point
count--
if count > max
max = count
result = x
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句