6 最小覆盖矩形(Smallest Rectangle Enclosing Black Pixels)
2021/7/8 6:05:56
本文主要是介绍6 最小覆盖矩形(Smallest Rectangle Enclosing Black Pixels),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 1 题目
- 2 描述
- 3 思路
- 3.1 图解
- 3.2 时间复杂度
- 3.3 空间复杂度
- 4 源码
1 题目
最小覆盖矩形(Smallest Rectangle Enclosing Black Pixels)
lintcode:题号——600,难度——hard
2 描述
一个由二进制矩阵表示的图,0 表示白色像素点,1 表示黑色像素点。黑色像素点是联通的,即只有一块黑色区域。像素是水平和竖直连接的,给一个黑色像素点的坐标 (x, y) ,返回囊括所有黑色像素点的矩阵的最小面积。
样例1:
输入:["0010","0110","0100"],x=0,y=2
输出:6
解释:矩阵左上角坐标是(0, 1), 右下角的坐标是(2, 2)
样例2:
输入:["1110","1100","0000","0000"], x = 0, y = 1
输出:6
解释:矩阵左上角坐标是(0, 0), 右下角坐标是(1, 3)
3 思路
从答案反向找思路,要得到面积,需要横向跨度和纵向跨度,横向需要分别找到最左边和最右边,纵向需要分别找到最上面和最下面,题中给出了一个种子点,即其中一个黑子所在的位置,从种子点分别向上、下、左、右四个方向看,例如向左的情况,需要找到最左端的黑子,而最左端的黑子不一定与种子点在同一行,所以我们要考虑整个左半矩阵图,由于只要找到最左端的横向坐标即可,不用关心列坐标,可以将左半矩阵图纵向压缩进同一行,这样只要该列存在任何黑子,则将压缩后形成的点标记为黑,因为所有的黑子是联通的,最后向左看的情况一定会形成“oooxxx”形式的数列,使用二分法即可找到最左端边缘。
按照相同的思路可以找到其他三个方向的边缘,然后得到横纵跨度,再得到面积。
- 考虑左半矩阵,以每列是否存在黑子为条件,二分查找最左边缘;
- 分别得到四个方向的边缘;
- 计算横纵跨度,得到面积。
扩展。
其实题目中给出的种子点有点奇怪,按照常理来判断给不给这个种子点的位置,都是能得到答案的,题中直接给出了,简化了这一步。题目也可以使用广度优先搜索来做,可以思考一下。
3.1 图解
graph TD X[0表示白子,1和X表示黑子,X为种子点<br/>'0, 0, 0, 0, 1, 0, 0'<br/>'0, 1, 1, 1, 1, 0, 0'<br/>'0, 0, 0, 1, X, 0, 0'<br/>'0, 0, 1, 1, 1, 1, 0'<br/>'0, 0, 0, 0, 0, 0, 0'] X -- 左半矩阵 --> A['0, 0, 0, 0, 1'<br/>'0, 1, 1, 1, 1'<br/>'0, 0, 0, 1, X'<br/>'0, 0, 1, 1, 1'<br/>'0, 0, 0, 0, 0'] X -- 上半矩阵 --> B['0, 0, 0, 0, 1, 0, 0'<br/>'0, 1, 1, 1, 1, 0, 0'<br/>'0, 0, 0, 1, X, 0, 0'] X -- 右半矩阵 --> C['1, 0, 0'<br/>'1, 0, 0'<br/>'X, 0, 0'<br/>'1, 1, 0'<br/>'0, 0, 0'] X -- 下半矩阵 --> D['0, 0, 0, 1, X, 0, 0'<br/>'0, 0, 1, 1, 1, 1, 0'<br/>'0, 0, 0, 0, 0, 0, 0'] A --> A0[列中出现一个黑子1,则压缩后的点为1] A0 -- 分列 --> A1[0<br/>0<br/>0<br/>0<br/>0] A0 -- 分列 --> A2[0<br/>1<br/>0<br/>0<br/>0] A0 -- 分列 --> A3[0<br/>1<br/>0<br/>1<br/>0] A0 -- 分列 --> A4[0<br/>1<br/>1<br/>1<br/>0] A0 -- 分列 --> A5[1<br/>1<br/>X<br/>1<br/>0] A1 -- 压缩 --> A11[0] A2 -- 压缩 --> A21[1] A3 -- 压缩 --> A31[1] A4 -- 压缩 --> A41[1] A5 -- 压缩 --> A51[1] A11 --> AA['0, 1, 1, 1, 1'] A21 --> AA A31 --> AA A41 --> AA A51 --> AA AA -- 二分查找得到左边缘<br/>下标都是指在整体矩阵中的下标 --> AAA[下标1] B -- 分行,压缩 --> BB['1'<br/>'1'<br/>'1'] BB -- 上边缘 --> BBB[下标0] C -- 分列,压缩 --> CC['1, 1, 0'] CC -- 右边缘 --> CCC[下标5] D -- 分行,压缩 --> DD['1'<br/>'1'<br/>'0'] DD -- 下边缘 --> DDD[下标3] AAA --> AC[跨度5] CCC --> AC BBB --> BD[跨度4] DDD --> BD AC --> R[面积20] BD --> R输入:["0000100","0111100","0001100","0011110","0000000"],
x = 2, y = 4
输出:20
3.2 时间复杂度
算法在每一个方向使用一次二分法,假定矩阵图有m行n列,相同维度的二分法耗时可以整体来算,横向上二分法操作的时间复杂度为O(log n)
,纵向上二分法操作的时间复杂度为O(log m)
。
横向的二分法每次判断都包含一次对列的遍历操作的时间复杂度O(m)
,纵向的二分法每次判断都包含一次对行的遍历的时间复杂度O(m)
。
横向二分法总耗时O(m * log n)
,纵向二分法总耗时O(n * log m)
。
算法的时间复杂度为O(m * log n + n * log m)
,其中m
为矩阵图的行数,n
为矩阵图的列数。
3.3 空间复杂度
算法的空间复杂度为O(1)
。
4 源码
注意事项:
- 题目给出的种子点坐标(x, y),x表示二维数组的行序号,y表示二维数组的列序号,所以x是纵向的距离,y是横向的距离,这点和直角坐标系的x方向和y方向刚好相反,很容易想歪,思路要清晰;
- 求面积的时候,注意一个点代表一距离,不是一条边代表一距离。
C++版本:
/** * @param image: 代表包含'0'和'1'为元素的二进制矩阵图 * @param x: 初始黑点的纵坐标 * @param y: 初始黑点的横坐标 * @return: 最小覆盖矩形的面积 */ int minArea(vector<vector<char>> &image, int x, int y) { // write your code here if (image.empty() || image.front().empty()) // 横纵都不能为空 { return 0; } int maxRow = image.size() - 1; int maxColumn = image.front().size() - 1; // 计算四个方向最边缘点的下标 int left = calLeftEdge(image, 0, y); int right = calRightEdge(image, y, maxColumn); int top = calTopEdge(image, 0, x); int bottom = calBottomEdge(image, x, maxRow); return (right - left + 1 ) * (bottom - top + 1); } // 计算最左边缘黑点的横坐标 int calLeftEdge(vector<vector<char>> & image, int start, int end) { int mid = 0; while (start + 1 < end) { mid = start + (end - start) / 2; if (isColWhite(image, mid)) { start = mid; } else { end = mid; } } if (isColWhite(image, start)) { return end; } else { return start; } } // 计算最右边缘黑点的横坐标 int calRightEdge(vector<vector<char>> & image, int start, int end) { int mid = 0; while (start + 1 < end) { mid = start + (end - start) / 2; if (isColWhite(image, mid)) { end = mid; } else { start = mid; } } if (isColWhite(image, end)) { return start; } else { return end; } } // 计算最上边缘黑点的纵坐标 int calTopEdge(vector<vector<char>> & image, int start, int end) { int mid = 0; while (start + 1 < end) { mid = start + (end - start) / 2; if (isRowWhite(image, mid)) { start = mid; } else { end = mid; } } if (isRowWhite(image, start)) { return end; } else { return start; } } // 计算最下边缘黑点的纵坐标 int calBottomEdge(vector<vector<char>> & image, int start, int end) { int mid = 0; while (start + 1 < end) { mid = start + (end - start) / 2; if (isRowWhite(image, mid)) { end = mid; } else { start = mid; } } if (isRowWhite(image, end)) { return start; } else { return end; } } // 判断行中是否全为白点 bool isRowWhite(vector<vector<char>> & image, int row) { for (int i = 0; i < image.front().size(); i++) { if (image.at(row).at(i) == '1') { return false; } } return true; } // 判断列中是否全为白点 bool isColWhite(vector<vector<char>> & image, int col) { for (int i = 0; i < image.size(); i++) { if (image.at(i).at(col) == '1') { return false; } } return true; }
这篇关于6 最小覆盖矩形(Smallest Rectangle Enclosing Black Pixels)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain