S*******e
发帖数: 379 | |
S*******e
发帖数: 379 | 2 顶，谁给帮忙确认一下？
【在 S*******e 的大作中提到】
: 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 的大作中提到】
: 不用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 的大作中提到】
: 不用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 的大作中提到】
: 不用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 的大作中提到】
: 不用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 的大作中提到】
:
: 我看了一下，觉得那个证明好像不太合理。事实上binary search可以每次排除掉四个
: submatrix中的三个，但是那个证明里证明的是四个sub matrix里面只可以排除掉两个
: 。
|
i*********7
发帖数: 348 | 10 我这样比较，假设我的矩阵是长m宽n，那么我每次比较的对象，就是a[m][n/2]以及a[m
/2][n]，这样比较，你就可以每次都取到四分之一个submatrix. |
i*********7
发帖数: 348 | |
