回馈地里,口音听起来不是国人不是烙印
一道题,给定一堆坐标点,(x, y)
求能组成的最小rectangle
长和宽都要和x轴y轴平行
回馈地里,口音听起来不是国人不是烙印
一道题,给定一堆坐标点,(x, y)
求能组成的最小rectangle
长和宽都要和x轴y轴平行
有点类似 蠡口其五菱。只不过这里dp[j][q] 改为上次 j 列 和 q 列 同时为 1 时候的所在行 i 是多少。
int minRectangles(vector<vector<int>>& grid) {
int row = grid.size(), col = grid[0].size();
map<int, map<int,int>> g;
unordered_map<int, unordered_map<int,int>> dp;
for(int i = 0; i < row; ++i) {
for(int j = 0; j < col; ++j) {
if(grid[i][j] == 1)
g[i][j] = 1;
}
}
int res = INT_MAX;
for(auto itr = g.begin(); itr != g.end(); ++itr) {
int i = itr->first;
for(auto jtr = g[i].begin(); jtr != g[i].end(); ++jtr) {
int j = jtr->first;
for(auto qtr = jtr; qtr != g[i].end(); ++qtr) {
int q = qtr->first;
int area = -1;
if(dp.find(j) != dp.end() && dp[j].find(q) != dp[j].end()) {
area = (q - j) * (i - dp[j][q]);
}
if(area > 0) {
res = min(res, area);
}
dp[j][q] = i;
}
}
}
return res;
}
这里因为不知道点的边界是多少,所以不能使用一个固定的二维matrix去遍历,所以使用二维map。
楼主觉得这样做可以吗?
public static int MinimumRect(int [][] arr){
int res = 100;
HashSet<String> set = new HashSet<>();
for(int [] a:arr){
set.add(makeString(a));
}
for(int i=0;i<arr.length;i++){
for(int j=i+1;j<arr.length;j++){
int[] leftBottom = arr[i];
int []rightTop = arr[j];
int []leftTop = new int[]{leftBottom[0], rightTop[1]};
String lt = makeString(leftTop);
int []rightBottom = new int[]{rightTop[0], leftBottom[1]};
String rb = makeString(rightBottom);
if(set.contains(lt) && set.contains(rb)){
int size = Math.abs((rightTop[0] - leftBottom[0]) * (rightTop[1] - leftBottom[1]));
if(size>0){
res = Math.min(res, size);
}
}
}
}
System.out.println(res);
return res;
}
public static String makeString(int[] a){
StringBuffer sb = new StringBuffer();
sb.append(String.valueOf(a[0]));
sb.append("-");
sb.append(String.valueOf(a[1]));
return sb.toString();
}
按照x值排序,x相同就排序y,然后二分法找出两两x之间的最小y值差,更新最小值。时间复杂度,排序O(nlogn)。查找最小y值差,有多少组x为M,最大一组x里面的y的数量为K。O(MKlogK)
感谢楼主分享,可以请问一下大致思路是什么样的吗?
請問是由4點做成長方形 還是兩點?
我大概是遍历所有的点然后找可以组成rect的其他点,然后找min。但是应该直接算xy差值就可以了。。。
四点 zszszszs
请问二分法在这里是怎么用的 可以详细说说吗
直接算xy差值的话怎么保证rect边和坐标轴平行呢。。。想不通求解释