原题链接在这里:
题目:
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.
题解:
- Use a HashMap to maintain all y of the same x.
- Then try to find the diagonal nodes, get one node from x and one node from y, if x[0] == y[0] || x[1] == y[1], skip, they can't be diagonal nodes.
- Else if in x[0] HashMap entry contains y[1] and in y[0] HashMap entry contains x[1], then x and y could diagonal nodes. Use it to update rectangle size.
- Time Complexity: O(n ^ 2). n = points.length.
- Space: O(n).
- AC Java:
- class Solution {
- public int minAreaRect(int[][] points) {
- if(points == null || points.length <4){
- return 0;
- }
- HashMap<Integer, Set<Integer>> hm = new HashMap<>();
- for(int [] p : points){
- hm.putIfAbsent(p[0], new HashSet<>());
- hm.get(p[0]).add(p[1]);
- }
- int res = Integer.MAX_VALUE;
- for(int [] p1 : points){
- for(int [] p2 : points){
- if(p1[0] == p2[0] || p1[1] == p2[1]){
- continue;
- }
- if(hm.get(p1[0]).contains(p2[1]) && hm.get(p2[0]).contains(p1[1])){
- res = Math.min(res, Math.abs(p2[0] - p1[0]) * Math.abs(p2[1] - p1[1]));
- }
- }
- }
- return res == Integer.MAX_VALUE ? 0 : res;
- }
- }
跟上 Minimum Area Rectangle II.
来源: http://www.bubuko.com/infodetail-3355383.html