统计点对的数目
难度:
标签:
题目描述
给你一个无向图，无向图由整数 n ，表示图中节点的数目，和 edges 组成，其中 edges[i] = [ui, vi] 表示 ui 和 vi 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。
第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目：
a < bcnt是与a或者b相连的边的数目，且cnt严格大于queries[j]。
请你返回一个数组 answers ，其中 answers.length == queries.length 且 answers[j] 是第 j 个查询的答案。
请注意，图中可能会有 多重边 。
示例 1：
输入：n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3] 输出：[6,5] 解释：每个点对中，与至少一个点相连的边的数目如上图所示。 answers[0] = 6。所有的点对(a, b)中边数和都大于2，故有6个； answers[1] = 5。所有的点对(a, b)中除了(3,4)边数等于3，其它点对边数和都大于3，故有5个。
示例 2：
输入：n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5] 输出：[10,10,9,8,6]
提示：
2 <= n <= 2 * 1041 <= edges.length <= 1051 <= ui, vi <= nui != vi1 <= queries.length <= 200 <= queries[j] < edges.length
代码结果
运行时间: 279 ms, 内存: 50.3 MB
/*
思路：
1. 构建一个图的数据结构来存储节点和边的关系。
2. 计算每个节点的度数（与该节点相连的边的数目）。
3. 对于每个查询，通过计算满足条件的点对的数目来得到结果。
4. 使用Java Stream来简化处理。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int[] countPairs(int n, int[][] edges, int[] queries) {
int[] degree = new int[n + 1];
Map<Integer, Integer>[] edgeCount = new Map[n + 1];
for (int i = 1; i <= n; i++) {
edgeCount[i] = new HashMap<>();
}
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
degree[u]++;
degree[v]++;
edgeCount[u].put(v, edgeCount[u].getOrDefault(v, 0) + 1);
edgeCount[v].put(u, edgeCount[v].getOrDefault(u, 0) + 1);
}
int[] sortedDegree = degree.clone();
Arrays.sort(sortedDegree);
return IntStream.range(0, queries.length)
.map(i -> {
int q = queries[i];
int total = 0;
int left = 1, right = n;
while (left < right) {
if (sortedDegree[left] + sortedDegree[right] > q) {
total += right - left;
right--;
} else {
left++;
}
}
for (int u = 1; u <= n; u++) {
for (int v : edgeCount[u].keySet()) {
if (degree[u] + degree[v] > q && degree[u] + degree[v] - edgeCount[u].get(v) <= q) {
total--;
}
}
}
return total;
}).toArray();
}
}解释
方法:
此题解采用了一种基于计数的方法，通过统计每个节点的度数，以及每种度数出现的频率，来高效计算满足条件的点对数量。主要步骤如下：
1. 计算每个节点的度数，并统计每条边出现的次数。
2. 使用度数统计来预计算所有可能的度数和的点对数量，这里忽略了多重边的特殊处理。
3. 调整计数以考虑多重边，即对于图中实际存在的每条边，调整其对应的度数和的点对计数。
4. 通过计算后缀和来快速回答每个查询，即对于每个查询值，计算所有度数和大于该查询值的点对数量。
时间复杂度:
O(E + d^2 + Q)
空间复杂度:
O(n + E + d + Q)
代码细节讲解
🦆
在题解中提到的`调整计数以考虑多重边`的过程是如何操作的？请详细解释其对点对计数的具体影响。
▷🦆
为何在计算所有可能的度数和的点对数量时，对于同一度数的节点使用了`c1 * (c1 - 1) // 2`的计算方式？这里的逻辑是什么？
▷🦆
题解中提到的后缀和数组是如何构建的，其在解题过程中具体扮演了什么角色？
▷