leetcode 497, 528. Random Point in Non-overlapping Rectangles | 497. 非重叠矩形中的随机点（Java）

小鱼儿 2022-09-11 04:28 65阅读 0赞

## 497. Random Point in Non-overlapping Rectangles ##

[https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/][https_leetcode.com_problems_random-point-in-non-overlapping-rectangles]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

大坑：面积包含边界，计算要注意+1，这种随机数的问题，没有固定的输出，调bug不好调啊…目前的方法是，手动指定random的值，遍历所有可能的random，看是否符合预期。

思路：  
1、先按照面积计算每个rectangle的权重  
2、根据权重选择rectangle的下标（参考[ 528. Random Pick with Weight][528. Random Pick with Weight]）  
3、选好rectangle后，根据范围随机生成横坐标x、纵坐标y

class Solution { 
        Random r;
        int N;
        int[][] rects;
        long[] weight; // 权重
        long[] weightSum; // 权重前缀和
    
        public Solution(int[][] rects) { 
            this.rects = rects;
            r = new Random();
            N = rects.length;
            weight = new long[N];
            weightSum = new long[N];
            for (int i = 0; i < N; i++) { 
                weight[i] = ((long) rects[i][2] + 1 - rects[i][0]) * ((long) rects[i][3] + 1 - rects[i][1]); // +1 因为包含边界！坑！！
            }
            weightSum[0] = 0;
            if (N > 1) weightSum[1] = weight[0];
            for (int i = 2; i < N; i++) { 
                weightSum[i] = weightSum[i - 1] + weight[i - 1];
            }
        }
    
        public int[] pick() { 
            // 根据权重选择一个rectangle
            long sum = weight[N - 1] + weightSum[N - 1];
            long rand = randLong(0, sum);
            // 反向查找randLong属于的index
            int L = 0;
            int R = N - 1;
            int index = -1;
            if (weightSum[N - 1] <= rand) { 
                index = N - 1;
            } else { 
                while (L < R) { 
                    int M = L + (R - L) / 2;
                    if (weightSum[M] == rand) { 
                        index = M;
                        break;
                    } else if (weightSum[M] < rand) { 
                        if (L == M) { 
                            index = M;
                            break;
                        }
                        L = M;
                    } else { 
                        R = M - 1;
                        if (weightSum[R] <= rand) { 
                            index = R;
                            break;
                        }
                    }
                }
                if (index == -1) index = L;
            }
            int[] rec = rects[index];
            long x = randLong(rec[0], rec[2] + 1);
            long y = randLong(rec[1], rec[3] + 1);
            return new int[]{ (int) x, (int) y};
        }
    
        public long randLong(long a, long b) {  // 左闭右开
            return a + (long) (Math.random() * (b - a));
        }
    
    }
    
    /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(rects); * int[] param_1 = obj.pick(); */

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 528. Random Pick with Weight ##

[https://leetcode.com/problems/random-pick-with-weight/][528. Random Pick with Weight]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
本题是上一题的一个子问题，直接复制粘贴了。

class Solution { 
        int N;
        int[] w; // 权重
        int[] wSum; // 权重前缀和
    
        public Solution(int[] w) { 
            N = w.length;
            this.w = w;
            wSum = new int[N];
            wSum[0] = 0;
            if (N > 1) wSum[1] = this.w[0];
            for (int i = 2; i < N; i++) { 
                wSum[i] = wSum[i - 1] + this.w[i - 1];
            }
        }
    
        public int pickIndex() { 
            // 根据权重选择一个rectangle
            int sum = w[N - 1] + wSum[N - 1];
            int rand = rand(0, sum);
            // 反向查找randLong属于的index
            int L = 0;
            int R = N - 1;
            int index = -1;
            if (wSum[N - 1] <= rand) { 
                index = N - 1;
            } else { 
                while (L < R) { 
                    int M = L + (R - L) / 2;
                    if (wSum[M] == rand) { 
                        index = M;
                        break;
                    } else if (wSum[M] < rand) { 
                        if (L == M) { 
                            index = M;
                            break;
                        }
                        L = M;
                    } else { 
                        R = M - 1;
                        if (wSum[R] <= rand) { 
                            index = R;
                            break;
                        }
                    }
                }
                if (index == -1) index = L;
            }
            return index;
        }
    
        public int rand(int a, int b) {  // 左闭右开
            return (int) (a + (Math.random() * (b - a)));
        }
    }
    
    /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(w); * int param_1 = obj.pickIndex(); */

[https_leetcode.com_problems_random-point-in-non-overlapping-rectangles]: https://leetcode.com/problems/random-point-in-non-overlapping-rectangles/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/2a8661c7df8240c2a30a912074d6db73.png
[528. Random Pick with Weight]: https://leetcode.com/problems/random-pick-with-weight/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/82379c5bdc5a4751bf337a9b306050c4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/dd15e38b31d64f6e80fbac7dcea3f69b.png