由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - 求集合包含,最快的算法是什么?
相关主题
请教一个算法问题 (转载)如何快速读入文本形式的整数
嵌入式系统用什么sorting算法比较好?Java数组怎么样能参数传递 (转载)
雨天哭求呀。问题请教
请问C#里面,如何对N个数组设置循环访问?问大家一个C语言编程的小问题
请教一个2维动态矩阵的问题请教 C/C++ 指向多维数组的指针的问题
[合集] 一个vector的问题搞不定,不得不问,一维数组跟二维数组的问题
再问:关于多维数组的malloc新手学JAVA,遇到一个难题,有大侠愿意帮忙吗?
[合集] C++delete数组遇到的问题另一个相关的很基础的问题
相关话题的讨论汇总
话题: pattern话题: 算法话题: 数组话题: row话题: expression
进入Programming版参与讨论
1 (共1页)
k****f
发帖数: 3794
1
给个二维的整数数组 a_{i,j},每行的整数个数都不一样的。
假定,同一行里面,没有重复的数字。不同行,可以有重复的数字。
这个a_{i,j}数组是固定不变的。
现在另外给一个一维数组b_k,要检索a中的行,
看看有没有哪个行被包含在b_k数组里面。就是这个行的所有数字,
都出现在b_k里面。
如果允许对a做预处理,用空间换时间,
不知道这个算法的时间复杂度能下降到什么程度。
X****r
发帖数: 3557
2
你把a_{i,j}转换成一个hash map
M(n) -> list of i for all i that exists j such that a_{i_j} = n
另外定义c_i为a_{i,j}的第i行的长度
这样算法就是
for all i
z_i <- c_i
for all k
for all i in M(b(k))
if --z_i == 0
return i

【在 k****f 的大作中提到】
: 给个二维的整数数组 a_{i,j},每行的整数个数都不一样的。
: 假定,同一行里面,没有重复的数字。不同行,可以有重复的数字。
: 这个a_{i,j}数组是固定不变的。
: 现在另外给一个一维数组b_k,要检索a中的行,
: 看看有没有哪个行被包含在b_k数组里面。就是这个行的所有数字,
: 都出现在b_k里面。
: 如果允许对a做预处理,用空间换时间,
: 不知道这个算法的时间复杂度能下降到什么程度。

s*****g
发帖数: 5159
3
Sort every row of a
Sort b
Compare sorted b with each row of sorted a.

【在 k****f 的大作中提到】
: 给个二维的整数数组 a_{i,j},每行的整数个数都不一样的。
: 假定,同一行里面,没有重复的数字。不同行,可以有重复的数字。
: 这个a_{i,j}数组是固定不变的。
: 现在另外给一个一维数组b_k,要检索a中的行,
: 看看有没有哪个行被包含在b_k数组里面。就是这个行的所有数字,
: 都出现在b_k里面。
: 如果允许对a做预处理,用空间换时间,
: 不知道这个算法的时间复杂度能下降到什么程度。

b***e
发帖数: 1419
4
Yes. But this still takes O(n^2) to do. In fact, O(n) can be achieved if
each row in a is considered a regular expression pattern. For instance,
if a is:
[1, 2, 3]
Then the pattern is:
1?2?3?
This way, the matrix A can be considered as a one regular expression
pattern (by disjoin constructions). Simply this pattern down to a DFA and
match b against it. This will bring it down to O(n).

【在 s*****g 的大作中提到】
: Sort every row of a
: Sort b
: Compare sorted b with each row of sorted a.

1 (共1页)
进入Programming版参与讨论
相关主题
另一个相关的很基础的问题请教一个2维动态矩阵的问题
数组指针的问题[合集] 一个vector的问题
面试题 -算法?再问:关于多维数组的malloc
如何将若干已升序排序好的数组合并在一起,并仍然是升序?[合集] C++delete数组遇到的问题
请教一个算法问题 (转载)如何快速读入文本形式的整数
嵌入式系统用什么sorting算法比较好?Java数组怎么样能参数传递 (转载)
雨天哭求呀。问题请教
请问C#里面,如何对N个数组设置循环访问?问大家一个C语言编程的小问题
相关话题的讨论汇总
话题: pattern话题: 算法话题: 数组话题: row话题: expression