如何免费做网站,设计素材网站推荐pin,苏醒主题wordpress,安徽长江建设集团有限公司网站文章目录1. 题目2. 解题1. 题目
给定在 xy 平面上的一组点#xff0c;确定由这些点组成的矩形的最小面积#xff0c;其中矩形的边平行于 x 轴和 y 轴。
如果没有任何矩形#xff0c;就返回 0。
示例 1#xff1a;
输入#xff1a;[[1,1],[1,3],[3,1],[3,3],[2,2]]
输出…
文章目录1. 题目2. 解题1. 题目
给定在 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
所有的点都是不同的。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-area-rectangle 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
枚举4个顶点是会超时的枚举对角线组合然后在哈希里检查另外两个顶点是否都存在
class Solution {
public:int minAreaRect(vectorvectorint points) {int i, j, area INT_MAX, s;unordered_mapint, unordered_setint m;for(auto p : points)m[p[0]].insert(p[1]);for(i 0; i points.size(); i)for(j i1; j points.size(); j){if(points[i][0]points[j][0] || points[i][1]points[j][1]|| !m[points[i][0]].count(points[j][1]) || !m[points[j][0]].count(points[i][1]))//i,j作为对角线另外两点不存在continue;s abs(points[i][0]-points[j][0])*abs(points[i][1]-points[j][1]);if(s area)area s;}return areaINT_MAX ? 0 : area;}
};1316 ms 18.8 MB
根据题目的数据范围哈希采用40001进制数压缩为一个int加快运行速度
class Solution {
public:int minAreaRect(vectorvectorint points) {int i, j, area INT_MAX, s;unordered_setint m;for(auto p : points)m.insert(p[0]*40001p[1]);for(i 0; i points.size(); i)for(j i1; j points.size(); j){if(points[i][0]points[j][0] || points[i][1]points[j][1]|| !m.count(points[i][0]*40001points[j][1]) || !m.count(points[j][0]*40001points[i][1]))//i,j作为对角线另外两点不存在continue;s abs(points[i][0]-points[j][0])*abs(points[i][1]-points[j][1]);if(s area)area s;}return areaINT_MAX ? 0 : area;}
};832 ms 17.1 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
