1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
int[][] xIntervals = new int[][] { { ax1, ax2 }, { bx1, bx2 } };
int[][] yIntervals = new int[][] { { ay1, ay2 }, { by1, by2 } };
Arrays.sort(xIntervals, (a, b) -> a[0] - b[0]);
Arrays.sort(yIntervals, (a, b) -> a[0] - b[0]);
int areaSum = (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1);
if (xIntervals[1][0] >= xIntervals[0][1] || yIntervals[1][0] >= yIntervals[0][1]) {
return areaSum;
}
int leftBound = xIntervals[1][0];
int rightBound = Math.min(xIntervals[0][1], xIntervals[1][1]);
int lowBound = yIntervals[1][0];
int upBound = Math.min(yIntervals[0][1], yIntervals[1][1]);
return areaSum - (rightBound - leftBound) * (upBound - lowBound);
}
}
|
最直接的想法. 如果没有overlap, 直接计算二者的面积即可. 有交叉的话, 计算一下交叉的面积是多少. 减去即可.
时间复杂度: O(1)
空间复杂度: O(1)
1
2
3
4
5
6
7
8
| class Solution {
public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
int leftBound = Math.max(ax1, bx1), rightBound = Math.max(Math.min(ax2, bx2), leftBound);
int bottomBound = Math.max(ay1, by1), upBound = Math.max(Math.min(ay2, by2), bottomBound);
return (ax1 - ax2) * (ay1 - ay2) + (bx1 - bx2) * (by1 - by2)
- (leftBound - rightBound) * (bottomBound - upBound);
}
}
|
这个方法绝了.
如果两个rectangle会overlap, 那么相交的左边界就是Math.max(ax1, bx1), 右边界就是Math.min(ax2, bx2). 如果不相交的? 那说明相交的区域为0, 我们强行让这个区域为0, 方法就是在求rightBound的时候, 如果二者不想交, Math.min(ax2, bx2)是小于leftBound的. 此时我们让rightBound等于leftBound即可. 等到时候计算相交区域的面积的时候, 我们会得到0. up和bottom bound同理.
时间复杂度和空间复杂度不变.
