497. Random Point in Non-overlapping Rectangles.md

497. Random Point in Non-overlapping Rectangles

---

leetcode Daily Challenge on August 22th, 2020.

---

Difficulty : Medium

Related Topics : Random、Binary Search

---

Given a list of non-overlapping axis-aligned rectangles rects, write a function pick which randomly and uniformily picks an integer point in the space covered by the rectangles.

Note:

• An integer point is a point that has integer coordinates.
• A point on the perimeter of a rectangle is included in the space covered by the rectangles.
• ith rectangle = rects[i] = [x1,y1,x2,y2], where [x1, y1] are the integer coordinates of the bottom-left corner, and [x2, y2] are the integer coordinates of the top-right corner.
• length and width of each rectangle does not exceed 2000.
• 1 <= rects.length <= 100
• pick return a point as an array of integer coordinates [p_x, p_y]
• pick is called at most 10000 times.

Example 1:

Input:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output:
[null,[4,1],[4,1],[3,3]]

Example 2:

Input:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output:
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

Explanation of Input Syntax:

• The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array of rectangles rects. pick has no arguments. Arguments are always wrapped with a list, even if there aren't any.

---

Solution

same as 528. Random Pick with Weight

• mine
  • Java
    • Runtime: 54 ms, faster than 99.51%, Memory Usage: 45.9 MB, less than 81.98% of Java online submissions

      Random random;
      int[] sum;
      int[][] rects;
      int n;
      public Solution(int[][] rects) {
          this.rects = rects;
          n = rects.length;
          random = new Random();
          sum = new int[n + 1];
          for(int i = 0; i < n; i++){
              sum[i + 1] = sum[i] + (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
          }
      }
      
      public int[] pick() {
          int next = random.nextInt(sum[n]);
          int l = 1, r = n;
          while(l < r){
              int mid = (l + r) >>> 1;
              if(next >= sum[mid]){
                  l = mid + 1;
              }else{
                  r = mid;
              }
          }
          int[] t = rects[l - 1];
          int w = t[2] - t[0] + 1;
          int h = t[3] - t[1] + 1;
          next = next - (sum[l] - w * h);
          return new int[]{t[0] + next % w, t[1] + next / w};
          //or
          //return new int[]{t[0] + next / h, t[1] + next % h};
      }
      

---

• the most votes

• Runtime: 56 ms, faster than 96.12%, Memory Usage: 45.9 MB, less than 82.29% of Java online submissions

  int[][] rects;
  List<Integer> psum = new ArrayList<>();
  int tot = 0;
  Random rand = new Random();
  
  public Solution(int[][] rects) {
      this.rects = rects;
      for (int[] x : rects){
          tot += (x[2] - x[0] + 1) * (x[3] - x[1] + 1);
          psum.add(tot);
      }
  }
  
  public int[] pick() {
      int next = rand.nextInt(tot);
  
      int lo = 0;
      int hi = rects.length - 1;
      while (lo != hi) {
          int mid = (lo + hi) >>> 1;
          if (next >= psum.get(mid)) lo = mid + 1;
          else hi = mid;
      }
  
      int[] x = rects[lo];
      int width = x[2] - x[0] + 1;
      int height = x[3] - x[1] + 1;
      int base = psum.get(lo) - width * height;
      next -= base;
      return new int[]{x[0] + next % width, x[1] + next / width};
  }
  

---