有没有一种有效的方法可以在常量 space 的排序范围数组中找到最频繁的数字

Question

我必须从已排序的范围数组中找到最频繁出现的数字（或众数）。该范围仅由包含在内的开始和结束数字组成。 例如 arr[0] 可以包含数字 {0, 3}，这意味着数字 {0, 1, 2, 3}。范围按起始编号排序，当起始编号相等时，它们按结束编号排序。均按升序排列。

数组中填充了 n 个这样的范围。我需要找到一种方法来找到出现在最多范围内的数字。

我想到了一个将所有数字遍历一次的解决方案，但这是在 O(n * m) 中，其中 m 是范围的平均长度。对于我正在处理的大小，这是一个非常慢的算法。

我也看过一些更快的解决方案，例如 this，但是当您无法轻易找到第 k 个数字时，我想不出一种有效的实现方法，因为范围可能大不相同尺码。

我目前正尝试在 C 中实现此功能，但非常感谢任何想法或处理此问题的资源链接。

Answer 1

1. 将每个范围 {a, b} 转换为两个事件“在 a 处加 1”和“在 b+1 处减 1”。
2. 按添加或减去位置的升序对事件进行排序。对于相同的位置，减去事件应该比添加事件来得早。
3. 执行事件并查看计算结果在哪个点最高。

例如，如果我们有 3 个范围 {0, 5}, {2, 9}, {4, 7}，每个范围将是这样的：

0123456789
------
  --------
    ----

排序的事件是：

• 0加1
• 1 加 2
• 加 1 到 4
• 1减6
• 1减8
• 1 减 10

执行这些事件，在执行第3个事件之后，执行第4个事件之前，该值变为最高的3。因此我们可以说最合适的数字是4和5。

时间复杂度为 O(N log N) 因为：

• O(N) 从范围到事件的转换
• O(N log N) 事件排序
• O(N) 次事件执行

存储事件的 space 复杂度为 O(N)。