g********r
发帖数: 89 | 1 版上看来的面经，row/column sorted matrix怎么能是算法是log(m)+log(n)?
*******
1. 二位矩阵，行列都sorted，每行的第一个数小于前一行的最后一个数，给一个
target，判断其在不在矩阵内
2. 如果没有第二个条件，如何搜索
3. 如何使算法是log(m) + log(n)，log的底数是多少 | h***s
发帖数: 45 | 2 应该是Leetcode的原题： “Search a 2D Matrix”
整个矩阵是一个已排序数组，长度是m x n，查找一个目标一般用二分法，时间复杂度
是:TO( log(2, mxn) )
演算一下就是：TO( log(2, m) + log(2, n) )
注释: log(x,y) 解释为以x为底y的对数。 | w******n
发帖数: 61 | 3 如果没有第二个条件的话貌似是leetcode上3sum closest的一部分
【在 g********r 的大作中提到】
: 版上看来的面经，row/column sorted matrix怎么能是算法是log(m)+log(n)?
: *******
: 1. 二位矩阵，行列都sorted，每行的第一个数小于前一行的最后一个数，给一个
: target，判断其在不在矩阵内
: 2. 如果没有第二个条件，如何搜索
: 3. 如何使算法是log(m) + log(n)，log的底数是多少
| g********r
发帖数: 89 | 4 没有第二个条件的话，只是行列排序，能做到log scale吗？
【在 h***s 的大作中提到】
: 应该是Leetcode的原题： “Search a 2D Matrix”
: 整个矩阵是一个已排序数组，长度是m x n，查找一个目标一般用二分法，时间复杂度
: 是:TO( log(2, mxn) )
: 演算一下就是：TO( log(2, m) + log(2, n) )
: 注释: log(x,y) 解释为以x为底y的对数。
| s**x
发帖数: 7506 | 5 sigh, with the second a condition, it is just regular binary search!
for N elements, binary search is logN.
here N = mn, so log(mn) = log(m) + log(n)
btw, cc150 has details solutions for this question without the second
condition( which is quite silly condition of course). |
|
