S*******e 发帖数: 379 | |
S*******e 发帖数: 379 | 2 顶,谁给帮忙确认一下?
【在 S*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://www.glassdoor.com/Interview/Find-a-number-in-a-matrix-wh : 一道老题,最后那个人说可以从左下角开始binary search,好像不work吧
|
i**********e 发帖数: 1145 | 3 不用binary search,从右上或者左下角开始.
右上角:
每次走左一步(如果target数字小于此数字)或走下一步(如果target大于此数字);
如果等于则返回true。
worst case nRows + nCols 完成。
有人已经证明不可能比 O(nRows + nCols) 更好:
http://www.quora.com/You-are-given-an-MxN-matrix-of-numbers-wit |
S*******e 发帖数: 379 | 4 哦,多谢!
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不用binary search,从右上或者左下角开始. : 右上角: : 每次走左一步(如果target数字小于此数字)或走下一步(如果target大于此数字); : 如果等于则返回true。 : worst case nRows + nCols 完成。 : 有人已经证明不可能比 O(nRows + nCols) 更好: : http://www.quora.com/You-are-given-an-MxN-matrix-of-numbers-wit
|
h****e 发帖数: 928 | 5 多谢!我对这道题的最优解法也是纠结了好久,总觉得binary search
是不行的,以前也在版上问过。看来O(M+N)就是最优解了。
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不用binary search,从右上或者左下角开始. : 右上角: : 每次走左一步(如果target数字小于此数字)或走下一步(如果target大于此数字); : 如果等于则返回true。 : worst case nRows + nCols 完成。 : 有人已经证明不可能比 O(nRows + nCols) 更好: : http://www.quora.com/You-are-given-an-MxN-matrix-of-numbers-wit
|
r**d 发帖数: 316 | 6 在那个链接里,li zhang的分析是对的,最优办法应该比线性略好一些
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不用binary search,从右上或者左下角开始. : 右上角: : 每次走左一步(如果target数字小于此数字)或走下一步(如果target大于此数字); : 如果等于则返回true。 : worst case nRows + nCols 完成。 : 有人已经证明不可能比 O(nRows + nCols) 更好: : http://www.quora.com/You-are-given-an-MxN-matrix-of-numbers-wit
|
i*********7 发帖数: 348 | 7 我会告诉你其实理论上存在logM + logN吗。。。 |
i*********7 发帖数: 348 | 8
我看了一下,觉得那个证明好像不太合理。事实上binary search可以每次排除掉四个
submatrix中的三个,但是那个证明里证明的是四个sub matrix里面只可以排除掉两个
。
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不用binary search,从右上或者左下角开始. : 右上角: : 每次走左一步(如果target数字小于此数字)或走下一步(如果target大于此数字); : 如果等于则返回true。 : worst case nRows + nCols 完成。 : 有人已经证明不可能比 O(nRows + nCols) 更好: : http://www.quora.com/You-are-given-an-MxN-matrix-of-numbers-wit
|
r**d 发帖数: 316 | 9 最坏情况不能排除3个吧,两个是可以的。(如果a[k,i]
a[k,i]和a[k,i+1]到a[m,n]两个矩形区域都可以排除。)
【在 i*********7 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我看了一下,觉得那个证明好像不太合理。事实上binary search可以每次排除掉四个 : submatrix中的三个,但是那个证明里证明的是四个sub matrix里面只可以排除掉两个 : 。
|
i*********7 发帖数: 348 | 10 我这样比较,假设我的矩阵是长m宽n,那么我每次比较的对象,就是a[m][n/2]以及a[m
/2][n],这样比较,你就可以每次都取到四分之一个submatrix. |
i*********7 发帖数: 348 | |