当前位置：首页 > news >正文

497. 返回随机非重叠矩形中的一个坐标点

news 来源：原创 2024/5/7 20:26:49

497. 非重叠矩形中的随机点

给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。

在给定的矩形覆盖的空间内的任何整数点都有可能被返回。

请注意，整数点是具有整数坐标的点。

实现 Solution 类:

Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。

示例 1：
在这里插入图片描述

输入:
[“Solution”, “pick”, “pick”, “pick”, “pick”, “pick”]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
输出:
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

解释：
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // 返回 [1, -2]
solution.pick(); // 返回 [1, -1]
solution.pick(); // 返回 [-1, -2]
solution.pick(); // 返回 [-2, -2]
solution.pick(); // 返回 [0, 0]

对于这一题，个人觉得非常有意义的一题，可能我们在解决实际生活问题的过程中，就能碰到这样的题目，很有价值去学一学解题代码如下：

typedef struct {
    int **data;
    int length;
    int *size;
    int sum;
    
   

} Solution;


Solution* solutionCreate(int** rects, int rectsSize, int* rectsColSize) {
    Solution *re=(Solution *)malloc(sizeof(Solution));
    re->length=rectsSize;
    re->data=(int **)malloc(sizeof(int *)*rectsSize);
    re->size=(int *)malloc(sizeof(int )*rectsSize);
    re->sum=0;

    for(int i=0;i<rectsSize;i++){
        re->data[i]=(int *)malloc(sizeof(int )*4);
        re->size[i]=(rects[i][2]-rects[i][0]+1)*(rects[i][3]-rects[i][1]+1);
        re->sum=re->sum+re->size[i];
        for(int j=0;j<4;j++){
            re->data[i][j]=rects[i][j];

        }
    }
    return re;

}


int* solutionPick(Solution* obj, int* retSize) {
    int  index=0;
    int p=rand();
    p=p%obj->sum+1;
    int z=0;
    for(int i=0;i<obj->length;i++){
        if(p>=z&&p<=z+obj->size[i]){
            index=i;
            break;
        }
        else{
            z=z+obj->size[i];
        }
    }
    int  pick_index=index;
    int x_range=obj->data[pick_index][2]-obj->data[pick_index][0]+1;
    int y_range=obj->data[pick_index][3]-obj->data[pick_index][1]+1;
    int x=rand()%x_range+obj->data[pick_index][0];
     int y=rand()%y_range+obj->data[pick_index][1];

     int *re=(int *)malloc(sizeof(int)*2);
     re[0]=x;
     re[1]=y;
     *retSize=2;
     return re;


}

void solutionFree(Solution* obj) {

}

/**
 * Your Solution struct will be instantiated and called as such:
 * Solution* obj = solutionCreate(rects, rectsSize, rectsColSize);
 * int* param_1 = solutionPick(obj, retSize);
 
 * solutionFree(obj);
*/