[Swift]LeetCode497. 非重叠矩形中的随机点 | Random Point in N

发布时间：2020-12-14 05:04:11 所属栏目：百科来源：网络整理

导读：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 coordin

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"]
[[[[1,1,5,5]]],[],[]] Output: [null,[4,1],[3,3]]

Example 2:

Input: 
["Solution","pick"]
[[[[-2,-2,-1,-1],[1,3,0]]],[]] Output: [null,[-1,-2],[2,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.

给定一个非重叠轴对齐矩形的列表?rects，写一个函数?pick?随机均匀地选取矩形覆盖的空间中的整数点。

提示：

整数点是具有整数坐标的点。
矩形周边上的点包含在矩形覆盖的空间中。
第?i?个矩形?rects [i] = [x1，y1，x2，y2]，其中?[x1，y1]?是左下角的整数坐标，[x2，y2]?是右上角的整数坐标。
每个矩形的长度和宽度不超过 2000。
1 <= rects.length?<= 100
pick?以整数坐标数组?[p_x,p_y]?的形式返回一个点。
pick?最多被调用10000次。?

示例 1：

输入: 
["Solution","pick"]
[[[[1,[]]
输出: 
[null,3]]

示例 2：

输入: 
["Solution","pick"]
[[[[-2,-2]]?

输入语法的说明：

输入是两个列表：调用的子例程及其参数。Solution的构造函数有一个参数，即矩形数组?rects。pick没有参数。参数总是用列表包装的，即使没有也是如此。

520ms

 1 class Solution {
 2 
 3     let rects : [[Int]]
 4     let w: [Int]
 5     let sum: Int
 6     
 7     init(_ rects: [[Int]]) {
 8         func area(_ a: [Int]) -> Int {
 9             return abs(a[2]-a[0]+1)*abs(a[3]-a[1]+1)
10         }
11         self.rects = rects
12         w = rects.reduce(into: [Int]()) { $0.append(area($1)+($0.last ?? 0))}
13         sum = rects.reduce(0) { $0+area($1) }
14     }
15         
16     func pick() -> [Int] {
17       let random = Int.random(in: 0...sum-1)
18         let i = searchInsert(w,random)
19       let r = rects[searchInsert(w,random)]
20       return [Int.random(in: r[0]...r[2]),Int.random(in: r[1]...r[3])]
21     }
22     
23     func searchInsert(_ nums: [Int],_ target: Int) -> Int {
24         var low = 0
25         var high = nums.count-1
26         while low <= high {
27             let middle = (low + high) / 2
28             if nums[middle] == target {
29                 return middle+1
30             } else if nums[middle] > target {
31                 high = middle - 1
32             } else {
33                 low = middle + 1
34             }
35         }
36         return low
37     }
38 }
39 
40 /**
41  * Your Solution object will be instantiated and called as such:
42  * let obj = Solution(rects)
43  * let ret_1: [Int] = obj.pick()
44  */
45  
46 /**
47  * Your Solution object will be instantiated and called as such:
48  * let obj = Solution(rects)
49  * let ret_1: [Int] = obj.pick()
50  */

Runtime:?844 ms

Memory Usage:?22.3 MB

 1 class Solution {
 2     var _rects:[[Int]]
 3 
 4     init(_ rects: [[Int]]) {
 5         _rects = rects        
 6     }
 7     
 8     func pick() -> [Int] {
 9         var sumArea:Int = 0
10         var selected:[Int] = [Int]()
11         for rect in _rects
12         {
13             var area:Int = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1)
14             sumArea += area
15             if Int.random(in: 0..<sumArea) < area
16             {
17                 selected = rect
18             }
19         }
20         var x:Int = Int.random(in: 0..<(selected[2] - selected[0] + 1)) + selected[0]
21         var y:Int = Int.random(in: 0..<(selected[3] - selected[1] + 1)) + selected[1]
22         return [x,y]      
23     }
24 }
25 
26 /**
27  * Your Solution object will be instantiated and called as such:
28  * let obj = Solution(rects)
29  * let ret_1: [Int] = obj.pick()
30  */
31

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!