Problem
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 <= 5000 <= points[i][0] <= 400000 <= points[i][1] <= 40000- All points are distinct.
Solution 1: HashTable + Brute Force
Try all pairs of points to form a diagonal and see whether pointers of another diagonal exist or not.
Assume two points are (x0, y0), (x1, y1) x0 != x1 and y0 != y1. The other two points will be (x0, y1), (x1, y0)
Time complexity: O(n^2)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua, running time: 96 ms class Solution { public: int minAreaRect(vector<vector<int>>& points) { unordered_map<int, unordered_set<int>> s; for (const auto& point : points) s[point[0]].insert(point[1]); const int n = points.size(); int min_area = INT_MAX; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { int x0 = points[i][0]; int y0 = points[i][1]; int x1 = points[j][0]; int y1 = points[j][1]; if (x0 == x1 || y0 == y1) continue; int area = abs(x0 - x1) * abs(y0 - y1); if (area > min_area) continue; if (!s[x1].count(y0) || !s[x0].count(y1)) continue; min_area = area; } return min_area == INT_MAX ? 0 : min_area; } }; |
C++ / 1D hashtable
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua, 68 ms class Solution { public: int minAreaRect(vector<vector<int>>& points) { unordered_set<int> s; for (const auto& point : points) s.insert((point[0] << 16) | point[1]); const int n = points.size(); int min_area = INT_MAX; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { int x0 = points[i][0]; int y0 = points[i][1]; int x1 = points[j][0]; int y1 = points[j][1]; if (x0 == x1 || y0 == y1) continue; int area = abs(x0 - x1) * abs(y0 - y1); if (area > min_area) continue; int p0 = (x1 << 16) | y0; int p1 = (x0 << 16) | y1; if (!s.count(p0) || !s.count(p1)) continue; min_area = area; } return min_area == INT_MAX ? 0 : min_area; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment