如何加速检测覆盖点的光线的算法？
如何加速检测覆盖点的光线的算法？
提问于 2022-10-04 12:53:08
“假设你有一条路(或数字线)，头上的灯照亮了一段数字线。灯光由一个2D阵列表示，索引I处的光线包括从arri到arri (包括)。
你也会得到这条线上点的列表，对于每一个点，你想要计算出有多少灯光照亮了这个点。我想返回一个列表，其中listi =照亮点I的灯数。“
示例输入/输出：lights = [[1, 7], [5, 11], [7, 9]], points = [7, 1, 5]应该返回[3, 1, 2]
我编写了一个解决方案，在该解决方案中，对于点中的每一个点，您可以在灯阵列上循环，并查看有多少个点具有<=点<=光点。这个解太慢(为O(n *k)，其中n= num。灯和k= num。))。我也试着把灯分类，当兰皮点的时候就断了，但还是超时了。有人能想到一个更快的算法来计算这个数组吗？我很难找到其他的方法来解决这个问题。
回答 1
Stack Overflow用户
回答已采纳
发布于 2022-10-04 15:15:38
这个问题最好这样解决：
- 从灯光数组中获取所有更改，并创建一个大小为其大小两倍的数组。它将有点和光的元组变化。光变化组件是+1还是-1，取决于该点代表光跨度的开始还是结束。当它结束时，这个点应该比在光阵列中多一个点，因此为了表明该点仍然是由光到达的，我们只应该在向右移动到下一个点时才对它进行折扣。
- 按点对此结果进行排序。可能会有重复的。
然后，
- 从左到右积累光的变化值，因此从左到右将所有这些-1和+1相加，并在发现光变化的点上再次存储中间结果。最后的累积值当然是0.
。
- 按点选择地使数组唯一，只保留大部分重复点的正确位置，因为这些点具有正确的累积值。(我没有在下面的implementation)
中这样做
- 最后对该数组使用二进制搜索将每个给定的点转换为在该点上发光的灯数。
执行情况：
from bisect import bisect
def solve(lights, points):
pairs = sorted((x + i, -i or 1) for changes in lights for i, x in enumerate(changes))
offsets, changes = zip(*pairs)
total = 0
cumul = [0] + [total := total + change for change in changes]
return [cumul[bisect(offsets, x)] for x in points]
lights = [[1, 7], [5, 11], [7, 9]]
points = [7, 1, 5]
print(solve(lights, points)) # [3, 1, 2]这是移除重复项的版本。只有当cumul列表中确实存在许多重复的抵消时，才会有好处：
def solve(lights, points):
pairs = sorted((x + i, -i or 1) for changes in lights for i, x in enumerate(changes))
total = 0
cumulpairs = [(x, total := total + change) for x, change in pairs]
# remove duplicates - assuming Python 3.7+ with ordered dicts
offsets, cumul = zip(*dict(cumulpairs).items())
cumul = [0] + list(cumul)
return [cumul[bisect(offsets, x)] for x in points]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/73948161
复制相关文章
相似问题
腾讯云开发者
