忽然觉得品冠这个名字很毛 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

忽然觉得品冠这个名字很毛

忽然觉得品冠这个名字很毛# Joke - 肚皮舞运动

g*r2014-03-21 07:03

1 楼

版上看来的面经，row/column sorted matrix怎么能是算法是log(m)+log(n)?
*******
1. 二位矩阵，行列都sorted，每行的第一个数小于前一行的最后一个数，给一个
target，判断其在不在矩阵内
2. 如果没有第二个条件，如何搜索
3. 如何使算法是log(m) + log(n)，log的底数是多少

h*s2014-03-21 07:03

2 楼

求2张，包子答谢。

m*r2014-03-21 07:03

3 楼

还姓黄...

h*s2014-03-21 07:03

4 楼

应该是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*n2014-03-21 07:03

5 楼

如果没有第二个条件的话貌似是leetcode上3sum closest的一部分

【在 g********r 的大作中提到】

: 版上看来的面经，row/column sorted matrix怎么能是算法是log(m)+log(n)?
: *******
: 1. 二位矩阵，行列都sorted，每行的第一个数小于前一行的最后一个数，给一个
: target，判断其在不在矩阵内
: 2. 如果没有第二个条件，如何搜索
: 3. 如何使算法是log(m) + log(n)，log的底数是多少

g*r2014-03-21 07:03

6 楼

没有第二个条件的话，只是行列排序，能做到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*x2014-03-21 07:03

7 楼

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).