h****e
发帖数: 928 | 1 就是这道题目：MxN的二维数组，每一行，每一列都排好序了。在这样的
数组中查找一个元素。
一般给出的解法是从左下角找起，向上或向右移。似乎二分法会错过
一些数。
以下是一个网站提出的解法和解释：
http://basicalgos.blogspot.com/2012/03/14-find-element-in-sorte
另外，这和LeetCode上的Search a 2D matrix题目不一样。 |
p*1
发帖数: 104 | 2 I think it should be o(log(n*m)) |
d**********x
发帖数: 4083 | 3 IIRC，二分的方法最终可证也是O(N+M)的，但是过程十分繁复
不如就直接找了。
【在 h****e 的大作中提到】
: 就是这道题目：MxN的二维数组，每一行，每一列都排好序了。在这样的
: 数组中查找一个元素。
: 一般给出的解法是从左下角找起，向上或向右移。似乎二分法会错过
: 一些数。
: 以下是一个网站提出的解法和解释：
: http://basicalgos.blogspot.com/2012/03/14-find-element-in-sorte
: 另外，这和LeetCode上的Search a 2D matrix题目不一样。
|
z**u
发帖数: 704 | 4 CLRS上有这个题，应该是O(M+N)
Give an O(m+n)-time algorithm to determine whether a given number is stored
in a given m × n Young tableau.
【在 h****e 的大作中提到】
: 就是这道题目：MxN的二维数组，每一行，每一列都排好序了。在这样的
: 数组中查找一个元素。
: 一般给出的解法是从左下角找起，向上或向右移。似乎二分法会错过
: 一些数。
: 以下是一个网站提出的解法和解释：
: http://basicalgos.blogspot.com/2012/03/14-find-element-in-sorte
: 另外，这和LeetCode上的Search a 2D matrix题目不一样。
|
t**********h
发帖数: 2273 | 5 你的这个题目是150上的原题，O（M+N）可以做。
另外之前版上有讨论一道和这个相似的题，但是matrix本身有一个附加条件，即下一行
的对应的element比这一行的这个element也要大。所以最终就转化为一个一维排好序的
数组了，然后二分O（lgn） |
e****e
发帖数: 418 | 6 Apply binary search on diagonal elements (0,0), ... (m-1,n-1).
When the number is not on the diagonal line, we can do the binary search
until:
A[r][s] < num < A[r+1][q]
Then we know num must be either in array A[r][s+1],... A[r][N-1] or A[r+1][0
],...A[r+1][q-1] if the matrix has the element.
The we do binary search on those two one-dimensional arrays one by one.
The running time is O(log(N+M)) |
z********i
发帖数: 568 | 7 1 2 3 4
8 7 6 5
9 10 11 12
可以是input吗？
【在 h****e 的大作中提到】
: 就是这道题目：MxN的二维数组，每一行，每一列都排好序了。在这样的
: 数组中查找一个元素。
: 一般给出的解法是从左下角找起，向上或向右移。似乎二分法会错过
: 一些数。
: 以下是一个网站提出的解法和解释：
: http://basicalgos.blogspot.com/2012/03/14-find-element-in-sorte
: 另外，这和LeetCode上的Search a 2D matrix题目不一样。
|
L********e
发帖数: 159 | 8 这个也是O(m+n)，需要查询两个子矩阵
[0
【在 e****e 的大作中提到】
: Apply binary search on diagonal elements (0,0), ... (m-1,n-1).
: When the number is not on the diagonal line, we can do the binary search
: until:
: A[r][s] < num < A[r+1][q]
: Then we know num must be either in array A[r][s+1],... A[r][N-1] or A[r+1][0
: ],...A[r+1][q-1] if the matrix has the element.
: The we do binary search on those two one-dimensional arrays one by one.
: The running time is O(log(N+M))
|
j********e
发帖数: 1192 | 9 恩，这个可能是 O((m+n)).
第1层1个矩阵，log(m+n)
第2层2个子矩阵，2*log((m+n)/2),
第3层4个子矩阵，4*log((m+n)/4)
所以总和是 sum( 2^i * (log(m+n) - i) ), i从0到log(m+n).
这个和最后应该是O(m+m).
【在 L********e 的大作中提到】
: 这个也是O(m+n)，需要查询两个子矩阵
:
: [0
|
f***n
发帖数: 117 | 10 这个m和n不等的时候对角线是怎么找的？
另外，如果从矩阵的最边上（横和竖）二分似乎也可行，也比较简单。
比如
1 2 4 5
3 8 10 19
4 9 12 20
要找10的话，
从1 3 4 9 12 20中二分找，到9和12 之间的时候，就可以把9左边和上面的全扔掉了，
就掉下
4 5
10 19
然后继续在这个小矩阵边上找。
复杂度是log(m+n) + log(m-1+n-1)+ .. + log(m-n)
不知道这个逼近应该是啥，数学忘光了。。
【在 j********e 的大作中提到】
: 恩，这个可能是 O((m+n)).
: 第1层1个矩阵，log(m+n)
: 第2层2个子矩阵，2*log((m+n)/2),
: 第3层4个子矩阵，4*log((m+n)/4)
: 所以总和是 sum( 2^i * (log(m+n) - i) ), i从0到log(m+n).
: 这个和最后应该是O(m+m).
:
|
h****e
发帖数: 928 | 11 多谢各位的回复。看来可以认为O(M+N)是面试时候能给出的最优解了。 |
