gpt4 book ai didi

algorithm - 在范围系列中找到最频繁重复的整数

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:51:02 25 4
gpt4 key购买 nike

我有这个练习,但我不知道我错过了什么。它实际上与现有问题非常相似,但不相同,解决方案可能也不相同。现有问题:Finding the most frequent number from a set of ranges -

问题:


给你 n 个范围 [ai, bi],范围是 [0, nd],其中 d 是一个恒定的正整数。 ai, bi 也是整数, 0 <= ai <= bi <= n d 对于每个 i (i = 1, ..., n)。

编写一个算法,找出在 [ai, bi] 范围内出现次数最多的整数 z。复杂度必须是线性的(作​​为 n、d 的函数)。


在我看来,这就像一个经典的计数/基数排序问题:使用 k = n 作为基数,排序的复杂度变为 O(d*n)。问题是,下一步怎么办?我有点坚持这一点。在相关问题中,假设范围只能是一定大小,而在我的问题中没有这样的假设,理论上可以有范围 [0, nd]以及介于两者之间的任何东西。

随机示例:

Input: [1, 3], [5, 10], [5, 11], [6, 17], [8, 9], [9, 21], [11, 15], [12, 12]Output: 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

关于algorithm - 在范围系列中找到最频繁重复的整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22584731/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com