google面试题求解

原帖地址:mitbbs

同学前两天去谷歌onsite,有一道题大意是这样的
给一个m*n的矩阵,每个点不是0就是1,所有值为1的点是连通的,给你一个点的坐标,
告诉你这个点的值是1,求一个最小的矩形,能把所有的1包括在内
同学给了一个n logm的算法,但是面试官并不满意,想问问各位还有更优的算法吗?