题目描述
给你一个 n x 2
的二维数组 points
,它表示二维平面上的一些点坐标,其中 points[i] = [x_i, y_i]
。
我们定义 x
轴的正方向为 右(x
轴递增的方向),x
轴的负方向为 左(x
轴递减的方向)。类似的,我们定义 y
轴的正方向为 上(y
轴递增的方向),y
轴的负方向为 下(y
轴递减的方向)。
你需要安排这 n
个人的站位,这 n
个人中包括 liupengsay 和小羊肖恩 。你需要确保每个点处 恰好 有 一个 人。同时,liupengsay 想跟小羊肖恩单独玩耍,所以 liupengsay 会以 liupengsay 的坐标为 左上角,小羊肖恩的坐标为 右下角 建立一个矩形的围栏(注意,围栏可能 不 包含任何区域,也就是说围栏可能是一条线段)。如果围栏的 内部 或者 边缘 上有任何其他人,liupengsay 都会难过。
请你在确保 liupengsay 不会 难过的前提下,返回 liupengsay 和小羊肖恩可以选择的 点对 数目。
注意,liupengsay 建立的围栏必须确保 liupengsay 的位置是矩形的左上角,小羊肖恩的位置是矩形的右下角。比方说,以 (1, 1)
,(1, 3)
,(3, 1)
和 (3, 3)
为矩形的四个角,给定下图的两个输入,liupengsay 都不能建立围栏,原因如下:
- 图一中,liupengsay 在
(3, 3)
且小羊肖恩在(1, 1)
,liupengsay 的位置不是左上角且小羊肖恩的位置不是右下角。 - 图二中,liupengsay 在
(1, 3)
且小羊肖恩在(1, 1)
,小羊肖恩的位置不是在围栏的右下角。
样例
输入:points = [[1,1],[2,2],[3,3]]
输出:0
解释:
没有办法可以让 liupengsay 的围栏以 liupengsay 的位置为左上角且小羊肖恩的位置为右下角。
所以我们返回 0。
输入:points = [[6,2],[4,4],[2,6]]
输出:2
解释:总共有 2 种方案安排 liupengsay 和小羊肖恩的位置,使得 liupengsay 不会难过:
- liupengsay 站在 (4, 4),小羊肖恩站在 (6, 2)。
- liupengsay 站在 (2, 6),小羊肖恩站在 (4, 4)。
不能安排 liupengsay 站在 (2, 6) 且小羊肖恩站在 (6, 2),因为站在 (4, 4) 的人处于围栏内。
输入:points = [[3,1],[1,3],[1,1]]
输出:2
解释:总共有 2 种方案安排 liupengsay 和小羊肖恩的位置,使得 liupengsay 不会难过:
- liupengsay 站在 (1, 1),小羊肖恩站在 (3, 1)。
- liupengsay 站在 (1, 3),小羊肖恩站在 (1, 1)。
不能安排 liupengsay 站在 (1, 3) 且小羊肖恩站在 (3, 1),因为站在 (1, 1) 的人处于围栏内。
注意围栏是可以不包含任何面积的,上图中第一和第二个围栏都是合法的。
限制
2 <= n <= 1000
points[i].length == 2
-10^9 <= points[i][0], points[i][1] <= 10^9
points[i]
点对两两不同。
算法
(离散化,二维部分和) $O(n^2)$
- 将点按照行和列分别进行离散化,将横纵坐标都映射到一个范围内。
- 构造二维前缀和数组。
- 枚举点对,使用二分前缀和判定点对组成的矩形范围内的部分和是否为 2。
时间复杂度
- 离散化的时间复杂度为 $O(n \log n)$。
- 枚举点对的时间复杂度为 $O(n^2)$,每次判定的时间为常数。
- 故总时间复杂度为 $O(n^2)$。
空间复杂度
- 需要 $O(n^2)$ 的额外空间存储离散化数组和二维前缀和数组。
C++ 代码
class Solution {
public:
int numberOfPairs(vector<vector<int>>& points) {
const int n = points.size();
vector<int> xs, ys;
for (const auto &p : points) {
xs.push_back(p[0]);
ys.push_back(p[1]);
}
sort(xs.begin(), xs.end());
const int cx = unique(xs.begin(), xs.end()) - xs.begin();
xs.resize(cx);
sort(ys.begin(), ys.end());
const int cy = unique(ys.begin(), ys.end()) - ys.begin();
ys.resize(cy);
vector<vector<int>> sum(cx + 1, vector<int>(cy + 1, 0));
for (auto &p : points) {
p[0] = lower_bound(xs.begin(), xs.end(), p[0]) - xs.begin() + 1;
p[1] = lower_bound(ys.begin(), ys.end(), p[1]) - ys.begin() + 1;
++sum[p[0]][p[1]];
}
for (int i = 1; i <= cx; i++)
for (int j = 1; j <= cy; j++)
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (i == j)
continue;
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
if (!(x1 <= x2 && y1 >= y2))
continue;
if (sum[x2][y1] - sum[x1 - 1][y1] - sum[x2][y2 - 1]
+ sum[x1 - 1][y2 - 1] == 2)
++ans;
}
return ans;
}
};