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