【算法题】查找vector在matrix里的位置

有一个n×m的数组和一个1×m的数组，如何查找这个1×m的数组位于n×m数组的第几行？
有可能位于不止一行，需要给出所有行号。

其实和在一个长字符串里找短字符串的问题略像。但是还是有不同。

看大家谁的方法速度最快～～

没人回复么？想试试是我没有权限还是真的没人回

每行都是m个数，就一个一个比呗，有不一样就换下一行。时间复杂度O(mn)？

先把matrix排序，用类似radix sort的方法，O(km)，然后查找这一行.

rogerdai 发表于 2013-5-15 18:00
先把matrix排序，用类似radix sort的方法，O(km)，然后查找这一行.

请问是sort哪些元素呢？第一列？如果每一行都sort又会变成O(mn)了吧

tianyeblack 发表于 2013-5-16 21:11
请问是sort哪些元素呢？第一列？如果每一行都sort又会变成O(mn)了吧

sort每一行，把m列分成k组来sort...类似radix sort..

最差情况肯定是O(nm)——如果每一列都匹配，那么必须所有mn个数字都检查过才能保证算法结束。所以任何优化都无法提高最差复杂度，只能针对平均复杂度进行优化。