e********3
发帖数: 229 | 1 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
比如:
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
0 0 1 0 0
0 0 0 0 0
最小矩阵就是 (1,1), (1,3), (3,1), (3,3) | a********5
发帖数: 1631 | 2 从给定的点开始DFS（或者BFS，时间复杂度一样）找这个联通区域的所有点。每次找的
时候如果这个点的坐标超出了当前已经找到的坐标范围就更新。最后得道的坐标范围就
是结果。
WORST CASE编历矩阵里的所有点。M*N。
【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
| l*********u
发帖数: 19053 | 3 从M*N外边向给定点，找第一个1，就是最小矩形的一边。找4次4边。
【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
| h*****e
发帖数: 34 | 4 这个方法不对。
要求是最小矩形，应该可以是斜着的矩形吧。
如下图：
010
101
010
最小矩形不是（0,0），（0,2），（2，0），（2,2），面积2*2=4
而是以四个1为顶点的斜着的矩形（0，1），（1，0),(2,1),(1,2)，面积为2
【在 l*********u 的大作中提到】
: 从M*N外边向给定点，找第一个1，就是最小矩形的一边。找4次4边。
| a********m
发帖数: 15480 | 5 不可能O(MN)以下吧。lower bound就是O(MN)。所以老老实实扫描一遍就完了。
只是有优化可以做。
【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
| l*********u
发帖数: 19053 | 6 good point
斜着的矩形,只能45度吧。转XY轴45度，再来4次。
【在 h*****e 的大作中提到】
: 这个方法不对。
: 要求是最小矩形，应该可以是斜着的矩形吧。
: 如下图：
: 010
: 101
: 010
: 最小矩形不是（0,0），（0,2），（2，0），（2,2），面积2*2=4
: 而是以四个1为顶点的斜着的矩形（0，1），（1，0),(2,1),(1,2)，面积为2
| e********3
发帖数: 229 | 7
面试官说可以优化,不过没给答案.这好像是COMPUTER VISION里的算法.
【在 a********m 的大作中提到】
: 不可能O(MN)以下吧。lower bound就是O(MN)。所以老老实实扫描一遍就完了。
: 只是有优化可以做。
| b***e
发帖数: 1419 | 8 Google问这题。有人贴过O(n*log(n))的方法：
只考虑找上边界，其他方向同理。在row坐标0和给定点之间按行做二分搜索。如果一行
全0，则向下继续搜，否则向上继续搜。一直找到某一行有1胆识它的上一行全0。
【在 e********3 的大作中提到】
:
: 面试官说可以优化,不过没给答案.这好像是COMPUTER VISION里的算法.
| e********3
发帖数: 229 | 9
我一开始也是想2分，但是后面发现不大对。比如：
0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0
0 1 0 1 0 1 0 0
0 0 0 1 1 0 0 0
0 0 1 1 0 0 0 0
假设给定（2，3），那你怎么做2分呢？同一行可以有很多0，1间隔，用2分怎么决定往
那边分？
【在 b***e 的大作中提到】
: Google问这题。有人贴过O(n*log(n))的方法：
: 只考虑找上边界，其他方向同理。在row坐标0和给定点之间按行做二分搜索。如果一行
: 全0，则向下继续搜，否则向上继续搜。一直找到某一行有1胆识它的上一行全0。
| b***e
发帖数: 1419 | 10 Here's what I suggest you do:
Read my post, carefully, character by character, and apply the algorithm as
described to you example. Hopefully you'll see how it works.
【在 e********3 的大作中提到】
:
: 我一开始也是想2分，但是后面发现不大对。比如：
: 0 0 0 0 0 0 0 0
: 0 1 1 1 1 1 1 0
: 0 1 0 1 0 1 0 0
: 0 0 0 1 1 0 0 0
: 0 0 1 1 0 0 0 0
: 假设给定（2，3），那你怎么做2分呢？同一行可以有很多0，1间隔，用2分怎么决定往
: 那边分？
| | | a********m
发帖数: 15480 | 11 看不懂。
咱来个简单case帮助理解。
100000*100000的图，只有最后一行的最后一个点是黑的，其他都是白。你说说怎么二
分吧。
as
【在 b***e 的大作中提到】
: Here's what I suggest you do:
: Read my post, carefully, character by character, and apply the algorithm as
: described to you example. Hopefully you'll see how it works.
| e********3
发帖数: 229 | 12 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
比如:
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
0 0 1 0 0
0 0 0 0 0
最小矩阵就是 (1,1), (1,3), (3,1), (3,3) | a********5
发帖数: 1631 | 13 从给定的点开始DFS（或者BFS，时间复杂度一样）找这个联通区域的所有点。每次找的
时候如果这个点的坐标超出了当前已经找到的坐标范围就更新。最后得道的坐标范围就
是结果。
WORST CASE编历矩阵里的所有点。M*N。
【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
| l*********u
发帖数: 19053 | 14 从M*N外边向给定点，找第一个1，就是最小矩形的一边。找4次4边。
【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
| h*****e
发帖数: 34 | 15 这个方法不对。
要求是最小矩形，应该可以是斜着的矩形吧。
如下图：
010
101
010
最小矩形不是（0,0），（0,2），（2，0），（2,2），面积2*2=4
而是以四个1为顶点的斜着的矩形（0，1），（1，0),(2,1),(1,2)，面积为2
【在 l*********u 的大作中提到】
: 从M*N外边向给定点，找第一个1，就是最小矩形的一边。找4次4边。
| a********m
发帖数: 15480 | 16 不可能O(MN)以下吧。lower bound就是O(MN)。所以老老实实扫描一遍就完了。
只是有优化可以做。
【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
| l*********u
发帖数: 19053 | 17 good point
斜着的矩形,只能45度吧。转XY轴45度，再来4次。
【在 h*****e 的大作中提到】
: 这个方法不对。
: 要求是最小矩形，应该可以是斜着的矩形吧。
: 如下图：
: 010
: 101
: 010
: 最小矩形不是（0,0），（0,2），（2，0），（2,2），面积2*2=4
: 而是以四个1为顶点的斜着的矩形（0，1），（1，0),(2,1),(1,2)，面积为2
| e********3
发帖数: 229 | 18
面试官说可以优化,不过没给答案.这好像是COMPUTER VISION里的算法.
【在 a********m 的大作中提到】
: 不可能O(MN)以下吧。lower bound就是O(MN)。所以老老实实扫描一遍就完了。
: 只是有优化可以做。
| b***e
发帖数: 1419 | 19 Google问这题。有人贴过O(n*log(n))的方法：
只考虑找上边界，其他方向同理。在row坐标0和给定点之间按行做二分搜索。如果一行
全0，则向下继续搜，否则向上继续搜。一直找到某一行有1胆识它的上一行全0。
【在 e********3 的大作中提到】
:
: 面试官说可以优化,不过没给答案.这好像是COMPUTER VISION里的算法.
| e********3
发帖数: 229 | 20
我一开始也是想2分，但是后面发现不大对。比如：
0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0
0 1 0 1 0 1 0 0
0 0 0 1 1 0 0 0
0 0 1 1 0 0 0 0
假设给定（2，3），那你怎么做2分呢？同一行可以有很多0，1间隔，用2分怎么决定往
那边分？
【在 b***e 的大作中提到】
: Google问这题。有人贴过O(n*log(n))的方法：
: 只考虑找上边界，其他方向同理。在row坐标0和给定点之间按行做二分搜索。如果一行
: 全0，则向下继续搜，否则向上继续搜。一直找到某一行有1胆识它的上一行全0。
| | | b***e
发帖数: 1419 | 21 Here's what I suggest you do:
Read my post, carefully, character by character, and apply the algorithm as
described to you example. Hopefully you'll see how it works.
【在 e********3 的大作中提到】
:
: 我一开始也是想2分，但是后面发现不大对。比如：
: 0 0 0 0 0 0 0 0
: 0 1 1 1 1 1 1 0
: 0 1 0 1 0 1 0 0
: 0 0 0 1 1 0 0 0
: 0 0 1 1 0 0 0 0
: 假设给定（2，3），那你怎么做2分呢？同一行可以有很多0，1间隔，用2分怎么决定往
: 那边分？
| a********m
发帖数: 15480 | 22 看不懂。
咱来个简单case帮助理解。
100000*100000的图，只有最后一行的最后一个点是黑的，其他都是白。你说说怎么二
分吧。
as
【在 b***e 的大作中提到】
: Here's what I suggest you do:
: Read my post, carefully, character by character, and apply the algorithm as
: described to you example. Hopefully you'll see how it works.
| b********r
发帖数: 620 | 23 大牛的意思是这样的：（以向上找为例）
因为给定的点是1，所以从任何2分的地方向该给定点靠近（如果该行没1）或者远离（
如果该行有1）。因为所有的1是连通的，所以，如果有的新发现的1点比该给定点更靠
近边界，那么，某个2分的线必然会碰到在某一行的1点。
用这点我们可以保证一定发现最高的1点。
【在 a********m 的大作中提到】
: 看不懂。
: 咱来个简单case帮助理解。
: 100000*100000的图，只有最后一行的最后一个点是黑的，其他都是白。你说说怎么二
: 分吧。
:
: as
| l******8
发帖数: 1691 | 24 这个好像leetcode上有的吧。记得好像只要recursive在周围四个点只要有1就转进过去
就行了，有几个1就转几次，然后找四面的极值。记得把当前点mark成0或者2（如果你
过后要恢复的话），或者你拿个set记下来visit过的1点，set会慢一点。
【在 e********3 的大作中提到】
: 给一个0,1矩阵M*N,里面有一块联通区域每个spot都是1.现任意给定此区域的一点,求出
: 一个最小的矩形能包围此区域.要求时间复杂度为O(MN)以下.
: 比如:
: 0 0 0 0 0
: 0 1 0 1 0
: 0 1 1 1 0
: 0 0 1 0 0
: 0 0 0 0 0
: 最小矩阵就是 (1,1), (1,3), (3,1), (3,3)
| w*****1
发帖数: 6807 | 25 这题和那个题还不太一样，不用翻转邻居什么的
不过核心思想都是BFS/DFS，这题更直接一点
【在 l******8 的大作中提到】
: 这个好像leetcode上有的吧。记得好像只要recursive在周围四个点只要有1就转进过去
: 就行了，有几个1就转几次，然后找四面的极值。记得把当前点mark成0或者2（如果你
: 过后要恢复的话），或者你拿个set记下来visit过的1点，set会慢一点。
|
|
