外星人建设的网站,汕头网站seo外包,服务器外面打不开网站,物流公司 网站模板题目链接 Leetcode.939 最小面积矩形 Rating #xff1a; 1752 题目描述
给定在 xy平面上的一组点#xff0c;确定由这些点组成的矩形的最小面积#xff0c;其中矩形的边平行于 x 轴和 y 轴。
如果没有任何矩形#xff0c;就返回 0。
示例 1#xff1a; 输入#xff1…题目链接 Leetcode.939 最小面积矩形 Rating 1752 题目描述
给定在 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 提示
1points.length5001 points.length 5001points.length5000points[i][0]400000 points[i][0] 400000points[i][0]400000points[i][1]400000 points[i][1] 400000points[i][1]40000所有的点都是不同的。
解法哈希表 枚举
对于每一个点 (x,y)我们都可以存入到一个哈希表 uset中。
因为每一个点的最大值是 40000。为了方便我们可以存入 x * 40001 y这样的一个数到 uset中。将两个点映射成一个数。
接下来枚举矩形的 左上角顶点(x1 , y1) 和 右下角顶点(x2 , y2)。 再判断另外两个顶点在不在集合中同时在的话就可以构成一个矩形。 时间复杂度O(n2)O(n^2)O(n2)
C代码
class Solution {
public:int minAreaRect(vectorvectorint points) {unordered_setint uset;for(auto p:points){uset.insert(p[0] * 40001 p[1]);}int n points.size();int s 1e9;for(int i 0;i n;i){int x1 points[i][0] , y1 points[i][1];for(int j i 1;j n;j){int x2 points[j][0] , y2 points[j][1];if(x1 x2 || y1 y2) continue;if(uset.count(x1 * 40001 y2) uset.count(x2 * 40001 y1)){int a abs(x1 - x2);int b abs(y1 - y2);s min(s,a * b);}}}return s 1e9 ? 0 : s;}
};
