• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode497.非重叠矩形中的随机点|RandomPointinNon-overlappingRectangles ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10391824.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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:

  1. An integer point is a point that has integer coordinates. 
  2. A point on the perimeter of a rectangle is included in the space covered by the rectangles. 
  3. 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.
  4. length and width of each rectangle does not exceed 2000.
  5. 1 <= rects.length <= 100
  6. pick return a point as an array of integer coordinates [p_x, p_y]
  7. pick is called at most 10000 times.

Example 1:

Input: 
[[[[1,1,5,5]]],[],[],[]]
Output: 
[null,[4,1],[4,1],[3,3]]

Example 2:

Input: 
[[[[-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 rectspick has no arguments. Arguments are always wrapped with a list, even if there aren't any.


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

提示:

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

示例 1:

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

示例 2:

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

输入语法的说明:

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


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  

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift-技巧(六)设置按钮状态并更改发布时间:2022-07-13
下一篇:
[Swift]LeetCode908.最小差值I|SmallestRangeI发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap