LeetCode - Minimum Area Rectangle
2024-10-15 01:28:18
Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes. If there isn't any rectangle, return 0. Example 1: Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4
Example 2: Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2 Note: 1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.
核心思想是利用对角线的原理定下两个点，根据对角线在找到另外两个点
如何把一个array pair存到hash里，第一次我用了int -> string, 超时了
class Solution {
public int minAreaRect(int[][] points) {
if(points == null || points.length == 0 || points[0].length ==0){
return -1;
}
Set<String> set = new HashSet<>();
for(int[] point : points){
set.add(Integer.toString(point[0])+":"+Integer.toString(point[1]));
}
int min = Integer.MAX_VALUE;
for(int i = 0; i < points.length-1; i++){
for(int j = i+1; j < points.length; j++){
int [] pointA = points[i];
int [] pointB = points[j];
if(pointA[0] != pointB[0] && pointA[1] != pointB[1]){
if(set.contains(Integer.toString(pointA[0])+":"+Integer.toString(pointB[1])) && set.contains(Integer.toString(pointB[0])+":"+Integer.toString(pointA[1]))){
int cur = Math.abs((pointB[0] - pointA[0]) * (pointB[1] - pointA[1]));
if(cur < min){
min = cur;
}
}
}
}
}
if(min == Integer.MAX_VALUE){
return 0;
}
return min;
}
}
第二次看了别人的代码， 原来可以按照把每一个pair的x存成key，y轴存成一个hashset。
class Solution {
public int minAreaRect(int[][] points) {
if(points == null || points.length == 0 || points[0].length ==0){
return 0;
}
Map<Integer, Set<Integer>> map = new HashMap<>();
for(int[] point : points){
if(map.containsKey(point[0])){
map.get(point[0]).add(point[1]);
}
else{
Set<Integer> set = new HashSet<Integer>();
set.add(point[1]);
map.put(point[0], set);
}
}
int min = Integer.MAX_VALUE;
for(int i = 0; i < points.length-1; i++){
for(int j = i+1; j < points.length; j++){
int [] pointA = points[i];
int [] pointB = points[j];
if(pointA[0] != pointB[0] && pointA[1] != pointB[1]){
if(map.get(pointA[0]).contains(pointB[1]) && map.get(pointB[0]).contains(pointA[1])){
int cur = Math.abs((pointB[0] - pointA[0]) * (pointB[1] - pointA[1]));
if(cur < min){
min = cur;
}
}
}
}
}
if(min == Integer.MAX_VALUE){
return 0;
}
return min;
}
}
最新文章
- 【Android】1.开发环境搭建
- B-Tree索引在sqlserver和mysql中的应用
- Tomcat端口被占用错误
- Qt实用小技巧（转）
- mysql 一些基础的语法和命令
- Brn系列商城4.1正式发布，欢迎大家下载体验
- Codeforces Round #199 (Div. 2) A Xenia and Divisors
- HDU 5583 Kingdom of Black and White 水题
- 集成支付宝SDK遇到的坑
- python基础之语句结束
- MyBatis动态代理
- 为什么我不推荐你使用vue-cli创建脚手架？
- 安卓Button-TextView-EditText综合运用
- 使用EF保存数据时 提示： 其他信息: 对一个或多个实体的验证失败。有关详细信息，请参阅“EntityValidationErrors”属性。
- 微信浏览器发送ajax请求执行多次解决方法
- C# Aspose.Cells.dll Excel操作总结
- 浅析python日志重复输出问题
- ES Terms 聚合数据不确定性
- 使用json-org包实现POJO和json的转换
- Buffer I/O error on device sr0