[Swift]LeetCode850. 矩形面积 II | Rectangle Area II

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

We are given a list of (axis-aligned) rectangles.  Each rectangle[i] = [x1, y1, x2, y2] , where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the ith rectangle.

Find the total area covered by all rectanglesin the plane.  Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: [[0,0,2,2],[1,0,2,3],[1,0,3,1]] Output: 6 Explanation: As illustrated in the picture.

Example 2:

Input: [[0,0,1000000000,1000000000]] Output: 49 Explanation: The answer is 10^18 modulo (10^9 + 7), which is (10^9)^2 = (-7)^2 = 49.

Note:

1 <= rectangles.length <= 200rectanges[i].length = 40 <= rectangles[i][j] <= 10^9The total area covered by all rectangles will never exceed 2^63 - 1 and thus will fit in a 64-bit signed integer.

---

我们给出了一个（轴对齐的）矩形列表 rectangles 。 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标，（x2，y2）是该矩形右上角的坐标。

找出平面中所有矩形叠加覆盖后的总面积。 由于答案可能太大，请返回它对 10 ^ 9 + 7 取模的结果。

示例 1：

输入：[[0,0,2,2],[1,0,2,3],[1,0,3,1]] 输出：6 解释：如图所示。

示例 2：

输入：[[0,0,1000000000,1000000000]] 输出：49 解释：答案是 10^18 对 (10^9 + 7) 取模的结果， 即 (10^9)^2 → (-7)^2 = 49 。

提示：

1 <= rectangles.length <= 200rectanges[i].length = 40 <= rectangles[i][j] <= 10^9矩形叠加覆盖后的总面积不会超越 2^63 - 1 ，这意味着可以用一个 64 位有符号整数来保存面积结果。

---

Runtime: 120 ms Memory Usage: 19.7 MB 1 class Solution { 2 func rectangleArea(_ rectangles: [[Int]]) -> Int { 3 var M:Int = 1000000007 4 var data:[Point] = [Point]() 5 for r in rectangles 6 { 7 data.append(Point(r[0], r[1], 1)) 8 data.append(Point(r[0], r[3], -1)) 9 data.append(Point(r[2], r[1], -1)) 10 data.append(Point(r[2], r[3], 1)) 11 } 12 data.sort(by:{(a:Point,b:Point) -> Bool in 13 if a.x == b.x {return b.y <= a.y} 14 return a.x < b.x}) 15 var map:[Int:Int] = [Int:Int]() 16 var preX:Int = -1 17 var preY:Int = -1 18 var result:Int = 0 19 for i in 0..<data.count 20 { 21 var p:Point = data[i] 22 map[p.y,default:0] += p.val 23 if i == data.count - 1 || data[i + 1].x > p.x 24 { 25 if preX > -1 26 { 27 result += (preY * (p.x - preX)) % M 28 result %= M 29 } 30 preY = calcY(map) 31 preX = p.x 32 } 33 } 34 return result 35 } 36 37 func calcY(_ p:[Int:Int]) -> Int 38 { 39 var result:Int = 0 40 var pre:Int = -1 41 var count:Int = 0 42 var nums = Set(p.keys).sorted(by:<) 43 for key in nums 44 { 45 if pre >= 0 && count > 0 46 { 47 result += key - pre 48 } 49 count += p[key,default:0] 50 pre = key 51 } 52 return result 53 } 54 } 55 56 class Point 57 { 58 var x:Int 59 var y:Int 60 var val:Int 61 init(_ x:Int,_ y:Int,_ val:Int) 62 { 63 self.x = x 64 self.y = y 65 self.val = val 66 } 67 }

 

转载于:https://www.cnblogs.com/strengthen/p/10593383.html