LeetCode 302. Smallest Rectangle Enclosing Black Pixels
DFS 最一开始想到的就是dfs,从题目给的点开始dfs搜索。 时间复杂度为O(mn) class Solution { public: int i_min=INT_MAX,i_max=INT_MIN; int j_min=INT_MAX,j_max=INT_MIN; vector<vector<int>> dirs={{1,0},{-1,{0,1},-1}}; int minArea(vector<vector<char>>& image,int x,int y) { dfs(image,x,y); return (i_max-i_min+1)*(j_max-j_min+1); } void dfs(vector<vector<char>>& image,int i,int j){ if (i<0 || i>=image.size() || j<0 || j>=image[0].size() || image[i][j]==‘0‘) return; i_min=min(i_min,i); i_max=max(i_max,i); j_min=min(j_min,j); j_max=max(j_max,j); image[i][j] = ‘0‘; for (auto dir:dirs){ dfs(image,i+dir[0],j+dir[1]); } } }; ? ? Binary Search 这道题给了一个坐标(x,y),其实是有用意的。如果只是单纯的搜索,我们完全可以搜索整个图。 这道题其实可以用二分来做。由于给定的点是黑的,我们可以从水平和竖直两个方向,分别找到由黑变白的点,和由白变黑的分界点。 其实类似投影的操作,把二维投影为一维的数组,然后从这个一维数组中寻找边界。而这个投影的过程可以在二分的时候一起完成。 最大的问题是二分。举个例子,比如 000111 找边界,我们可以用和 lower_bound 一样的思路去做。搜索区间 [low,high),解区间 [low,high], 同时,如果当前是投影到水平方向,我们要搜索 image[mid][i] 来判断这个元素的值;如果是投影到竖直方向,同理。这样的好处是把投影的过程和二分一起做,否则投影只能先处理好,而生成投影数组时间复杂度为 O(mn)。而这样和二分一起处理的话,水平和竖直方向时间复杂度分别为 O(mlogn) 和 O(nlogm)。 ? class Solution { public: int minArea(vector<vector<char>>& image,int y) { int m=image.size(),n=image[0].size(); int left=HorizontalSearch(image,0,y,m,true); int right=HorizontalSearch(image,y+1,n,false); int top=VerticalSearch(image,true); int bottom=VerticalSearch(image,x+1,false); return (right-left)*(bottom-top); } // [low,high) // if whiteToBlack,find the first black,otherwise find the first white int HorizontalSearch(vector<vector<char>> &image,int low,int high,int top,int bottom,bool whiteToBlack){ while (low<high){ int mid=(low+high)/2,k=top; bool isWhite=true; while (k<bottom) if (image[k][mid]==‘1‘) {isWhite=false; break;} else ++k; if (isWhite==whiteToBlack) low=mid+1; else high=mid; } return low; } int VerticalSearch(vector<vector<char>> &image,int left,int right,k=left; bool isWhite=true; while (k<right) if (image[mid][k]==‘1‘) {isWhite=false; break;} else ++k; if (isWhite==whiteToBlack) low=mid+1; else high=mid; } return low; } }; /* Equivalent: if (isWhite==whiteToBlack) low = mid+1; else high = mid; if (whiteToBlack){ if (isWhite) low=mid+1; else high=mid; }else{ if (isWhite) high=mid; else low=mid+1; } */ 其实水平和竖直也可以写在一起,只要添加一个变量判断即可,但是为了思路更清晰,我分开来写。 本题要特别注意二分的写法,用开区间来做。 时间复杂度 O(mlogn+nlogm) 空间复杂度 O(1) ? References: https://leetcode.com/problems/smallest-rectangle-enclosing-black-pixels/solution/ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |