题目描述
给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。
计算点对 (A, B) 的数量，其中
A 在 B 的左上角，并且- 它们形成的长方形中（或直线上）没有其它点（包括边界）。
返回数量。
示例 1：
输入：points = [[1,1],[2,2],[3,3]]
输出：0
解释：
没有办法选择 A 和 B，使得 A 在 B 的左上角。
示例 2：
输入：points = [[6,2],[4,4],[2,6]]
输出：2
解释：
- 左边的是点对
(points[1], points[0])，其中 points[1] 在 points[0] 的左上角，并且形成的长方形内部是空的。
- 中间的是点对
(points[2], points[1])，和左边的一样是合法的点对。
- 右边的是点对
(points[2], points[0])，其中 points[2] 在 points[0] 的左上角，但 points[1] 在长方形内部，所以不是一个合法的点对。
示例 3：
输入：points = [[3,1],[1,3],[1,1]]
输出：2
解释：
- 左边的是点对
(points[2], points[0])，其中 points[2] 在 points[0] 的左上角并且在它们形成的直线上没有其它点。注意两个点形成一条线的情况是合法的。
- 中间的是点对
(points[1], points[2])，和左边一样也是合法的点对。
- 右边的是点对
(points[1], points[0])，它不是合法的点对，因为 points[2] 在长方形的边上。
提示：
2 <= n <= 50points[i].length == 20 <= points[i][0], points[i][1] <= 50points[i] 点对两两不同。
解法
方法一：排序 + 枚举
我们不妨考虑枚举矩形左上角的点 $(x_1, y_1)$，那么根据题目，右下角的点 $(x_2, y_2)$ 随着 $x$ 的增大，纵坐标 $y$ 也会要严格增大，才符合题意。
因此，我们对所有点按照 $x$ 坐标升序排序，如果 $x$ 坐标相同，按照 $y$ 坐标降序排序。
然后我们枚举左上角的点 $(x_1, y_1)$，并且维护一个最大的 $y_2$，记为 $maxY$，表示所有右下角的点的纵坐标的最大值。然后我们枚举右下角的点 $(x_2, y_2)$，如果 $y_2$ 大于 $maxY$ 并且小于等于 $y_1$，那么我们就找到了一个合法的方案，将答案加一，然后更新 $maxY$ 为 $y_2$。
枚举完所有的点对后，我们就得到了答案。
时间复杂度 $O(n^2)$，空间复杂度 $O(\log n)$。其中 $n$ 是点的数量。
| class Solution:
def numberOfPairs(self, points: List[List[int]]) -> int:
points.sort(key=lambda x: (x[0], -x[1]))
ans = 0
for i, (_, y1) in enumerate(points):
max_y = -inf
for _, y2 in points[i + 1 :]:
if max_y < y2 <= y1:
max_y = y2
ans += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution {
public int numberOfPairs(int[][] points) {
Arrays.sort(points, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int ans = 0;
int n = points.length;
final int inf = 1 << 30;
for (int i = 0; i < n; ++i) {
int y1 = points[i][1];
int maxY = -inf;
for (int j = i + 1; j < n; ++j) {
int y2 = points[j][1];
if (maxY < y2 && y2 <= y1) {
maxY = y2;
++ans;
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public:
int numberOfPairs(vector<vector<int>>& points) {
sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0] || (a[0] == b[0] && b[1] < a[1]);
});
int n = points.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
int y1 = points[i][1];
int maxY = INT_MIN;
for (int j = i + 1; j < n; ++j) {
int y2 = points[j][1];
if (maxY < y2 && y2 <= y1) {
maxY = y2;
++ans;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | func numberOfPairs(points [][]int) (ans int) {
sort.Slice(points, func(i, j int) bool {
return points[i][0] < points[j][0] || points[i][0] == points[j][0] && points[j][1] < points[i][1]
})
for i, p1 := range points {
y1 := p1[1]
maxY := math.MinInt32
for _, p2 := range points[i+1:] {
y2 := p2[1]
if maxY < y2 && y2 <= y1 {
maxY = y2
ans++
}
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | function numberOfPairs(points: number[][]): number {
points.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]));
const n = points.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
const [_, y1] = points[i];
let maxY = -Infinity;
for (let j = i + 1; j < n; ++j) {
const [_, y2] = points[j];
if (maxY < y2 && y2 <= y1) {
maxY = y2;
++ans;
}
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | public class Solution {
public int NumberOfPairs(int[][] points) {
Array.Sort(points, (a, b) => a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
int ans = 0;
int n = points.Length;
int inf = 1 << 30;
for (int i = 0; i < n; ++i) {
int y1 = points[i][1];
int maxY = -inf;
for (int j = i + 1; j < n; ++j) {
int y2 = points[j][1];
if (maxY < y2 && y2 <= y1) {
maxY = y2;
++ans;
}
}
}
return ans;
}
}
|