前言
最近公司比較閑，那么自己也找點(diǎn)事情做龙巨。這道題呢在我寫這篇文章的時候谷歌笼呆、百度上都沒有答案，于是乎自己就來解答一下旨别。
題目
最小面積矩形
鏈接可能點(diǎn)不進(jìn)去诗赌，所以我把完整的題目寫在了下面。
描述：給定在 xy 平面上的一組點(diǎn)秸弛，確定由這些點(diǎn)組成的矩形的最小面積铭若，其中矩形的邊平行于 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
所有的點(diǎn)都是不同的。
題意很容易理解绞铃，就是找到所有能構(gòu)成矩形的4個點(diǎn)镜雨，然后求出它們的最小面積。示例1儿捧，最小面積為4由[[1,1],[1,3],[3,1],[3,3]]4個點(diǎn)構(gòu)成荚坞；示例2挑宠，面積為2由[[3,1],[3,3],[4,1],[4,3]]4個點(diǎn)構(gòu)成。
分析
看了題就知道這個題的難點(diǎn)在哪里：如何找到能構(gòu)成矩形的4個點(diǎn)颓影。于是乎我經(jīng)歷了下面的解題過程各淀。
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個點(diǎn)能不能構(gòu)成矩形
int areaRect(vector<int> one,vector<int> two,
vector<int> three,vector<int> four) {
///我就不貼代碼了碎浇，說一下思路：
///1：統(tǒng)計4個點(diǎn)的x、y是否分別是兩個值咆畏，并且分別都出現(xiàn)了2次南捂；
///2：得出面積。
}
Accept
于是乎我們轉(zhuǎn)變一下思路，借助于這道題钮蛛，我想到的方法是：我先固定兩個存在的x1鞭缭、x2，然后在兩個x1魏颓、x2上找對應(yīng)相等的每對y1岭辣、y2即可，那么x1甸饱、x2和每對y1沦童、y2這4個點(diǎn)肯定能構(gòu)成矩形。
比如：[[1,3],[3,1],[3,3],[1,3],[1,2]]叹话。
我們發(fā)現(xiàn)只有兩個x：1偷遗、3，然后我們在x為1和3之上去找y驼壶，發(fā)現(xiàn)有兩個相等的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循環(huán)固定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īng)的y進(jìn)行遍歷般妙，找到交集
set<int> leftYs = mapIterator->second;
set<int> rightYs = tempIterator->second;
//現(xiàn)在我們需要從leftYs和rightYs中找到交集
set<int> unionSet;
setIterator = leftYs.begin();
while (setIterator != leftYs.end()) {
if(rightYs.find(*setIterator) != rightYs.end()) {
unionSet.insert(*setIterator);
}
setIterator ++;
}
//如果沒有兩個數(shù)相等纪铺，則直接下一個循環(huán)，說明不存在y1股冗、y2
if(unionSet.size() < 2) {
continue;
}
//找到y(tǒng)1霹陡、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;
這個代碼還是很通俗易懂的，當(dāng)然了還有可以優(yōu)化的地方，可以用位運(yùn)算來做烹棉。
后記
數(shù)據(jù)結(jié)構(gòu)攒霹、算法和設(shè)計模式作為軟件開發(fā)的三大基礎(chǔ)，做算法也就相當(dāng)于同時練習(xí)了數(shù)據(jù)結(jié)構(gòu)和算法浆洗，意義還是很大的催束。有些算法題看到題目后確實一點(diǎn)思路都沒有，不過不要慌伏社，算法也是一個不斷學(xué)習(xí)的過程抠刺。時間長了，你也就會做了摘昌。
