方法一:Sort By Column
先Group by column,并排序。对于每个col,枚举所有的(r1, r2) pair,把pair作为key,col作为value保存到map,即 map[{r1,r2}] = col。如果之后再遍历到同样的pair,说明可以形成一个长方形。
需要注意的是,如果要用unordered_map且用pair作为key的话,需要写hash function来hash。
How to create an unordered_map of pairs in C++?
方便起见可以牺牲一点时间复杂度用map。还有一种解决方法是避免用pair作为key:由于本题给了数据范围,可以用 40001*x+y 来encode坐标。
class Solution { public: int minAreaRect(vector<vector<int>>& points) { map<int,vector<int>> m; // col -> group of row with this col for (auto point:points){ int c=point[0], r=point[1]; m[c].push_back(r); } int min_area=INT_MAX; map<pair<int,int>,int> last_col; // (r1,r2) -> the last column they are in for (auto it=m.begin();it!=m.end();++it){ int c=it->first; vector<int> &vec=it->second; sort(vec.begin(),vec.end()); for (int i=0;i<vec.size();++i){ for (int j=i+1;j<vec.size();++j){ int r1=vec[i], r2=vec[j]; if (last_col.count({r1,r2})){ min_area = min(min_area, (c-last_col[{r1,r2}])*(r2-r1) ); } last_col[{r1,r2}] = c; } } } return min_area<INT_MAX?min_area:0; } };
时间复杂度:O(n^3) [last_col用unordered_map的情况]
还有别的类似的做法,如首先 group by col,枚举一对col作为矩形边界(两者间的距离为长),然后two pointer找最短的宽。时间复杂度也是 O(n^3)。
方法二:Count by Diagonal
首先将所有点放到hashtable里。枚举一对点作为长方形的对角的两个点,这样另外两个定点的坐标也确定了下来。我们只需要检查这两个点在不在hashtable里即可。这里的问题和上面一样,pair做key的问题。
以下方法思路类似,但可以避免用pair做key。
class Solution { public: int minAreaRect(vector<vector<int>>& points) { map<int,unordered_set<int>> m; // col -> group of row with this col for (auto point:points){ m[point[0]].insert(point[1]); } int min_area=INT_MAX; for (int i=0;i<points.size();++i){ for (int j=i+1;j<points.size();++j){ int c1=points[i][0], r1=points[i][1]; int c2=points[j][0], r2=points[j][1]; if (c1==c2 || r1==r2) continue; if (m[c1].count(r2) && m[c2].count(r1)){ min_area = min(min_area, abs(r1-r2)*abs(c1-c2)); } } } return min_area<INT_MAX?min_area:0; } };
时间复杂度:O(n^2)