[Swift]LeetCode939.最小面积矩形|MinimumAreaRectangle

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn't any rectangle, return 0.

Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Example 2:

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2

Note:

1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.

给定在 xy 平面上的一组点，确定由这些点组成的矩形的最小面积，其中矩形的边平行于 x 轴和 y 轴。

如果没有任何矩形，就返回 0。

示例 1：

输入：[[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：4

示例 2：

输入：[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
输出：2

提示：

1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
所有的点都是不同的。

1672ms

 1 class Solution {
 2     func minAreaRect(_ points: [[Int]]) -> Int {
 3         var xAxeDict: [Int:Set<Int>] = [:]
 4         var yAxeDict: [Int:Set<Int>] = [:]
 5         var pointsCoords: Set<String> =  []
 6         for (ind, point) in points.enumerated() {
 7             if var set = xAxeDict[point[0]] {
 8                 set.insert(ind)
 9                 xAxeDict[point[0]] = set
10             } else {
11                 xAxeDict[point[0]] = Set([ind])
12             }
13             
14             if var set = yAxeDict[point[1]] {
15                 set.insert(ind)
16                 yAxeDict[point[1]] = set
17             } else {
18                 yAxeDict[point[1]] = Set([ind])
19             }
20         }
21         
22         var pointsToConsider: Set<Int> = []
23         for (key, value) in xAxeDict {
24             if value.count < 2 {
25                 continue
26             }
27             
28             for pointInd in value {
29                 if yAxeDict[points[pointInd][1]]!.count > 1 {
30                     pointsToConsider.insert(pointInd)
31                     pointsCoords.insert("\(points[pointInd][0])_\(points[pointInd][1])")
32                 }
33             }
34         }
35         
36         var pointsArr = Array(pointsToConsider)
37         pointsArr.sort()
38         
39         var result: Int? = nil
40         
41         for pointInd in pointsArr {
42             let x1 = points[pointInd][0]
43             let y1 = points[pointInd][1]
44             let xPeers = xAxeDict[x1]!
45             let yPeers = yAxeDict[y1]!
46             
47             for xPeer in xPeers {
48                 if xPeer <= pointInd {
49                     continue
50                 }
51                 let y2 = points[xPeer][1]
52                 for yPeer in yPeers {
53                     if yPeer <= pointInd {
54                         continue
55                     }
56                     let x2 = points[yPeer][0]
57                     if pointsCoords.contains("\(x2)_\(y2)") {
58                         result = min(abs((x2 - x1) * (y2 - y1)), result ?? Int.max)
59                     }
60                 }
61             }
62             
63         }
64         
65         return result ?? 0
66     }
67 }

2100ms

 1 class Solution {
 2     func minAreaRect(_ points: [[Int]]) -> Int {
 3         var xDict: [Int: Set<Int>] = [:], yDict: [Int: Set<Int>] = [:]
 4         
 5         for array in points {
 6             let x = array[0], y = array[1]
 7             if xDict[x] == nil {
 8                 xDict[x] = Set<Int>()
 9             }
10             xDict[x]!.insert(y)
11 
12             if yDict[y] == nil {
13                 yDict[y] = Set<Int>()
14             }
15             yDict[y]!.insert(x)
16         }
17         
18         var res = Int.max
19         for (x, setY) in xDict {
20             var i = 0, j = 1, arrayY = Array(setY)
21             for i in 0..<arrayY.count {
22                 for j in 1..<arrayY.count {
23                     if arrayY[i] == arrayY[j] { continue }
24                     if let set = yDict[arrayY[i]] {
25                         for item in set {
26                             if item == x { continue }
27                             if let setX = yDict[arrayY[j]], setX.contains(item) {
28                                 res = min(res, abs(arrayY[j] - arrayY[i]) * abs(item - x))
29                             }
30                         }
31                     }
32                 }
33             }
34         }
35  
36         return res == Int.max ? 0 : res
37     }
38 }

2296ms

 1 class Solution {
 2         struct Point:Hashable{
 3             var x:Int;
 4             var y:Int;
 5         }
 6         func minAreaRect(_ points: [[Int]]) -> Int {
 7             var minArea = Int.max;
 8             let pointSet = points.map{
 9                 (onePoint:[Int]) -> Point in
10                 return Point(x:onePoint[0],y:onePoint[1])
11             }
12             let set = Set<Point>(pointSet);
13             for lowerLeft in pointSet{
14                 for upperRight in pointSet{
15                     if lowerLeft.x < upperRight.x && lowerLeft.y < upperRight.y && set.contains(Point(x: lowerLeft.x, y: upperRight.y)) && set.contains(Point(x:upperRight.x,y: lowerLeft.y)){
16                         let area = (upperRight.x - lowerLeft.x)*(upperRight.y - lowerLeft.y)
17                         if (area < minArea) {
18                             minArea = area;
19                         }
20                     }
21                 }
22             }
23             return minArea == Int.max ? 0 : minArea;
24         }
25     }

2432ms

 1 class Solution {
 2     func minAreaRect(_ points: [[Int]]) -> Int {
 3         var n:Int = points.count
 4         var set:Set<Int64> = Set<Int64>()
 5         for i in 0..<n
 6         {
 7             set.insert(Int64(points[i][0]<<32|points[i][1]))
 8         }
 9         
10         var ret:Int = Int.max
11         for i in 0..<n
12         {
13             for j in (i + 1)..<n
14             {
15                 let S:Int64 = abs(Int64((points[i][0]-points[j][0])*(points[i][1]-points[j][1])))
16                 if S == 0 {continue}
17                 var x:Int64 = Int64(points[i][0]<<32|points[j][1])
18                 if !set.contains(x) {continue}
19                 x = Int64(points[j][0]<<32|points[i][1])
20                 if !set.contains(x) {continue}
21                 ret = min(ret, Int(S))
22             }
23         }
24         if ret == Int.max {return 0}
25         return ret
26     }
27 }

2924ms

 1 class Solution {
 2     struct Point_Dng: Hashable{
 3         var x: Int
 4         var y: Int
 5         
 6         init(_ x: Int, _ y: Int) {
 7             self.x = x
 8             self.y = y
 9         }
10         
11         var hashValue: Int{
12             return x * 100000 + y
13         }
14         
15         
16         static func == (_ lhs: Point_Dng, _ rhs: Point_Dng) -> Bool{
17             return lhs.x == rhs.x && lhs.y == rhs.y
18         }
19     }
20     
21     func minAreaRect(_ points: [[Int]]) -> Int {
22         let points_new = points.map({ (point: [Int]) -> Point_Dng in
23             return Point_Dng(point[0], point[1])
24         })
25         let set = Set(points_new)
26         var ans = Int.max
27         for point in points{
28             
29             for point_piece in points{
30                 
31                 
32                 if point[0] != point_piece[0] , point[1] != point_piece[1] , set.contains(Point_Dng(point[0], point_piece[1])) ,set.contains(Point_Dng(point_piece[0], point[1])) {
33                     
34                     ans = min(ans, abs((point_piece[1] - point[1] ) * (point_piece[0] - point[0])))
35                 }
36 
37             }
38         }
39         
40         if ans == Int.max {
41             return 0
42         }
43         else{
44             return ans
45         }
46 
47     }
48 }