狗店

回馈地里,口音听起来不是国人不是烙印

一道题,给定一堆坐标点,(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边和坐标轴平行呢。。。想不通求解释