前言
最近公司比较闲，那么自己也找点事情做。这道题呢在我写这篇文章的时候谷歌、百度上都没有答案，于是乎自己就来解答一下。
题目
最小面积矩形
链接可能点不进去，所以我把完整的题目写在了下面。
描述：给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。
如果没有任何矩形，就返回0。
示例 1：
输入：[[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4
示例 2：
输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
输出：2
提示：
1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
所有的点都是不同的。
题意很容易理解，就是找到所有能构成矩形的4个点，然后求出它们的最小面积。示例1，最小面积为4由[[1,1],[1,3],[3,1],[3,3]]4个点构成；示例2，面积为2由[[3,1],[3,3],[4,1],[4,3]]4个点构成。
分析
看了题就知道这个题的难点在哪里：如何找到能构成矩形的4个点。于是乎我经历了下面的解题过程。
Time Limit Exceeded
首先能直接想到的就是穷举了，代码也是出奇的简单。
int minAreaRect(vector<vector<int>>& points) {
int minAreaValue = INT_MAX;
//暴力穷举
for (int i = 0; i < points.size() - 3; i ++) {
for (int j = i + 1; j < points.size() - 2; j ++) {
for (int k = j + 1; k < points.size() - 1; k ++) {
for (int l = k + 1; l < points.size(); l ++) {
int value = areaRect(points[i],points[j],
points[k],points[l]);
if(value == -1) {
continue;
}
minAreaValue = min(minAreaValue,value);
}
}
}
}
return minAreaValue == INT_MAX ? 0 : minAreaValue;
}
//这4个点能不能构成矩形
int areaRect(vector<int> one,vector<int> two,
vector<int> three,vector<int> four) {
///我就不贴代码了，说一下思路：
///1：统计4个点的x、y是否分别是两个值，并且分别都出现了2次；
///2：得出面积。
}
暴力求解无法AC
Accept
于是乎我们转变一下思路，借助于这道题，我想到的方法是：我先固定两个存在的x1、x2，然后在两个x1、x2上找对应相等的每对y1、y2即可，那么x1、x2和每对y1、y2这4个点肯定能构成矩形。
比如：[[1,3],[3,1],[3,3],[1,3],[1,2]]。
我们发现只有两个x：1、3，然后我们在x为1和3之上去找y，发现有两个相等的y：1、3，那么答案也就是abs(x2 - x1) * abs(y2 - y1) = 4了。
int minValue = INT_MAX;
//x为key，相同x的y为value
unordered_map<int, set<int>> pointMap;
unordered_map<int, set<int>>::iterator mapIterator,tempIterator;
for (int index = 0; index < points.size(); index ++) {
pointMap[points[index][0]].insert(points[index][1]);
}
mapIterator = pointMap.begin();
set<int>::iterator setIterator;
// while (mapIterator != pointMap.end()) {
// cout<<"key:"<<mapIterator->first<<" ";
// set<int> numbers = mapIterator->second;
// setIterator = numbers.begin();
// while (setIterator != numbers.end()) {
// cout<<*setIterator<<" ";
// setIterator ++;
// }
// cout<<endl;
// mapIterator ++;
// }
mapIterator = pointMap.begin();
//双重for循环固定x1、x2
for (; mapIterator != pointMap.end(); mapIterator ++) {
tempIterator = mapIterator;tempIterator ++;
for (; tempIterator != pointMap.end(); tempIterator ++) {
int leftX = mapIterator->first;
int rightX = tempIterator->first;
//对两个x对应的y进行遍历，找到交集
set<int> leftYs = mapIterator->second;
set<int> rightYs = tempIterator->second;
//现在我们需要从leftYs和rightYs中找到交集
set<int> unionSet;
setIterator = leftYs.begin();
while (setIterator != leftYs.end()) {
if(rightYs.find(*setIterator) != rightYs.end()) {
unionSet.insert(*setIterator);
}
setIterator ++;
}
//如果没有两个数相等，则直接下一个循环，说明不存在y1、y2
if(unionSet.size() < 2) {
continue;
}
//找到y1、y2的最小差值
int minSubValue = INT_MAX;
for (setIterator = unionSet.begin(); setIterator != unionSet.end(); setIterator ++) {
set<int>::iterator temp = setIterator; temp ++;
if(temp == unionSet.end()) { break; }
minSubValue = min(minSubValue,*temp - *setIterator);
}
minValue = min(minValue,minSubValue * abs(leftX - rightX));
}
}
return minValue == INT_MAX ? 0 : minValue;
这个代码还是很通俗易懂的，当然了还有可以优化的地方，可以用位运算来做。
后记
数据结构、算法和设计模式作为软件开发的三大基础，做算法也就相当于同时练习了数据结构和算法，意义还是很大的。有些算法题看到题目后确实一点思路都没有，不过不要慌，算法也是一个不断学习的过程。时间长了，你也就会做了。
网友评论