25 – 09 -03
虽然这题 $2\leq n\leq 50$ 的数据范围相当小导致暴力 $O(n^3)$ 也能过，但你看标题后面的 I 就知道这玩意八成还有后续(搞不好就是明天每日一题)，而且肯定要扩数据范围，这种情况下 $O(n^3)$ 不优化基本必炸无疑。
—— 回旋镖
这盛世如你所愿，今日份数据范围：
- $2\leq n\leq 1000$
- $points.length == 2$
- $-10^9\leq points[i][0],points[i][1]\leq 10^9$
- $points $ 内各点各不相同
题目不摆了，换了更花里胡哨的说法但目标都是一样的，求左上和右下两点构成的矩形内部(含边界)不能有其他点的点对数量。
昨天 $O(n^2 )$ 的 pass 代码是能过的，但既然写了这篇就显然想说的不止这些
昨天那题的思路很朴素，开个遍历维护一下高度一路扫过去，这类似于一个区间查询操作所以收尾时我想到了线段树，但是线段树只是将单词查询操作的时间复杂度降低到 $O(\log n)$，但我们遍历所有点进行统计的操作必定是 $O(n^2)$ ，所以从这个角度看除非实现算法类似于 dp 不需要双重遍历，否则还是只是修修补补而不是改头换面(
当然并不是说修修补补就没有意义，换个角度重新出发，除了在遍历时维护第二高度进行筛选外我们是否还有其他方法？
有的兄弟，
有的这样的算法有九个咳，我思路是俩
一个就是上文提及的线段树，不过作为典型的空间换时间的算法，开线段树的花销其实也相当大，借用评论区手撕了持久化线段树的大佬的话
“可持久化线段树常数比较大，此做法运行效率并不高”
还有一个思路就是前缀和，预处理左上到右下的矩阵，记录该区间内点的数量，当 matrix[i][j] - matrix[i + a][j + b] = 2 时显然构成的矩形符合要求。
不过需要注意一下的就是数据范围 $-10^9\leq points[i][0],points[i][1]\leq 10^9$ 我想这个应该没人直接开数组狠狠爆内存空间，离散化一下就好了
懒得敲了，离散用的是 ArrayList 所以效率爆了..
class Solution {
public int numberOfPairs(int[][] points) {
int n = points.length;
if (n < 2) {
return 0;
}
// 排序
Arrays.sort(points, (int[] o1, int[] o2)->{
if(o1[0] == o2[0]) return Integer.compare(o2[1], o1[1]);
return Integer.compare(o1[0], o2[0]);
});
// 离散化
List<Integer> xList = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (i == 0 || points[i][0] != points[i-1][0]) {
xList.add(points[i][0]);
}
}
int nx = xList.size();
Set<Integer> ySet = new HashSet<>();
for (int[] p : points) {
ySet.add(p[1]);
}
List<Integer> yList = new ArrayList<>(ySet);
Collections.sort(yList);
int ny = yList.size();
// 二维前缀和
int[][] grid = new int[nx][ny];
int[] pointIX = new int[n];
int[] pointIY = new int[n];
for (int i = 0; i < n; i++) {
int x = points[i][0];
int y = points[i][1];
int ix = Collections.binarySearch(xList, x);
int iy = Collections.binarySearch(yList, y);
pointIX[i] = ix;
pointIY[i] = iy;
grid[ix][iy]++;
}
int[][] prefs = new int[nx+1][ny+1];
for (int i = 0; i < nx; i++) {
for (int j = 0; j < ny; j++) {
prefs[i+1][j+1] = prefs[i][j+1] + prefs[i+1][j] - prefs[i][j] + grid[i][j];
}
}
// 统计
int count = 0;
for (int i = 0; i < n; i++) {
int ix_b = pointIX[i];
int iy_b = pointIY[i];
for (int j = 0; j < i; j++) {
if (points[j][1] >= points[i][1]) {
int ix_a = pointIX[j];
int iy_a = pointIY[j];
int total = prefs[ix_b+1][iy_a+1] - prefs[ix_a][iy_a+1] - prefs[ix_b+1][iy_b] + prefs[ix_a][iy_b];
if (total == 2) {
count++;
}
}
}
}
return count;
}
}
一番操作猛如虎，一看时间复杂度 还是 $O(n^2)$
可喜可贺(
以上
发表回复