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.
|
|