按要求查找矩阵位置
Find matrix position by requirements
我有一个关于矩阵的问题。
有一个矩阵和一个段列表。
每个段都有名称、起点或终点以及描述起点和终点是指矩阵的行还是列的值。
可以有多个段同名(但起点和终点不同)。
现在我们有了一个名字列表(a、b、c)。
任务是找到位置适合的每个矩阵位置(x,y)
进入具有列表名称的每个段的范围(起点和终点)。
最快的方法是什么?
我需要这个来找到 KV 图中逻辑表达式的位置。
如果同名区间不重叠,那么很容易想出复杂度为 O(r * c * n) 的算法。 r = #rows, c = #columns and n = #names.
用0初始化一个r*c计数矩阵
对于每个名字...
对于名称为 ...
的每个区间
将区间内的计数矩阵的所有值增加1。
遍历计数矩阵和 return 计数 == n 的所有单元格。
如果同名区间不重叠,则每个名字n最多增加r * c个值,所以复杂度为O(r * c * n),其中+ r * c最后一步无关紧要。
我有一个关于矩阵的问题。
有一个矩阵和一个段列表。 每个段都有名称、起点或终点以及描述起点和终点是指矩阵的行还是列的值。
可以有多个段同名(但起点和终点不同)。
现在我们有了一个名字列表(a、b、c)。
任务是找到位置适合的每个矩阵位置(x,y) 进入具有列表名称的每个段的范围(起点和终点)。
最快的方法是什么?
我需要这个来找到 KV 图中逻辑表达式的位置。
如果同名区间不重叠,那么很容易想出复杂度为 O(r * c * n) 的算法。 r = #rows, c = #columns and n = #names.
用0初始化一个r*c计数矩阵
对于每个名字...
对于名称为 ...
的每个区间
将区间内的计数矩阵的所有值增加1。
遍历计数矩阵和 return 计数 == n 的所有单元格。
如果同名区间不重叠,则每个名字n最多增加r * c个值,所以复杂度为O(r * c * n),其中+ r * c最后一步无关紧要。