Hard
题目描述
给你一个整数 n 和一个二维整数数组 edges，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间有一条无向边。同时给你一个整数数组 queries。
定义 incident(a, b) 为连接到节点 a 或节点 b 的边数。
第 j 个查询的答案是满足以下两个条件的节点对 (a, b) 的数量：
a < bincident(a, b) > 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. 所有的点对都有 incident(a, b) 值大于 2。
- answers[1] = 5. 除了 (3, 4) 以外的所有点对都有 incident(a, b) 值大于 3。
示例 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 * 10^41 <= edges.length <= 10^51 <= ui, vi <= nui != vi1 <= queries.length <= 200 <= queries[j] < edges.length
解题思路
这道题的关键在于理解 incident(a, b) 的定义：连接到节点 a 或节点 b 的边数。这实际上等于 degree[a] + degree[b] - shared(a, b)，其中 shared(a, b) 是节点 a 和 b 之间的共享边数。
基本思路：
计算每个节点的度数：遍历所有边，统计每个节点的度数。
统计共享边数：对于每条边
(u, v)，增加shared[u][v]的计数。暴力方法：对于每个查询，遍历所有节点对
(a, b)（其中a < b），检查degree[a] + degree[b] - shared[a][b] > query。
优化方法（推荐）：
由于 shared[a][b] 通常很小（大部分为0），我们可以：
- 先假设所有
shared[a][b] = 0，用双指针技术快速统计满足degree[a] + degree[b] > query的节点对数量。 - 然后减去因为
shared[a][b] > 0而不再满足条件的节点对数量。
具体步骤：
- 将度数数组排序，使用双指针统计满足条件的对数
- 遍历所有有共享边的节点对，调整计数
这种方法的时间复杂度更优，特别是当图比较稀疏时。
代码实现
class Solution {
public:
vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
vector<int> degree(n + 1, 0);
map<pair<int, int>, int> shared;
// 计算度数和共享边数
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
degree[u]++;
degree[v]++;
if (u > v) swap(u, v);
shared[{u, v}]++;
}
// 对度数排序用于双指针
vector<int> sortedDegree(degree.begin() + 1, degree.end());
sort(sortedDegree.begin(), sortedDegree.end());
vector<int> result;
for (int query : queries) {
int count = 0;
// 双指针统计满足 degree[i] + degree[j] > query 的对数
int left = 0, right = n - 1;
while (left < right) {
if (sortedDegree[left] + sortedDegree[right] > query) {
count += right - left;
right--;
} else {
left++;
}
}
// 减去因共享边而不满足条件的对数
for (auto& [pair, cnt] : shared) {
int u = pair.first, v = pair.second;
if (degree[u] + degree[v] > query &&
degree[u] + degree[v] - cnt <= query) {
count--;
}
}
result.push_back(count);
}
return result;
}
};
class Solution:
def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:
degree = [0] * (n + 1)
shared = defaultdict(int)
# 计算度数和共享边数
for u, v in edges:
degree[u] += 1
degree[v] += 1
if u > v:
u, v = v, u
shared[(u, v)] += 1
# 对度数排序用于双指针
sorted_degree = sorted(degree[1:])
result = []
for query in queries:
count = 0
# 双指针统计满足 degree[i] + degree[j] > query 的对数
left, right = 0, n - 1
while left < right:
if sorted_degree[left] + sorted_degree[right] > query:
count += right - left
right -= 1
else:
left += 1
# 减去因共享边而不满足条件的对数
for (u, v), cnt in shared.items():
if (degree[u] + degree[v] > query and
degree[u] + degree[v] - cnt <= query):
count -= 1
result.append(count)
return result
public class Solution {
public int[] CountPairs(int n, int[][] edges, int[] queries) {
int[] degree = new int[n + 1];
Dictionary<(int, int), int> shared = new Dictionary<(int, int), int>();
// 计算度数和共享边数
foreach (var edge in edges) {
int u = edge[0], v = edge[1];
degree[u]++;
degree[v]++;
if (u > v) (u, v) = (v, u);
shared[(u, v)] = shared.GetValueOrDefault((u, v), 0) + 1;
}
// 对度数排序用于双指针
int[] sortedDegree = new int[n];
Array.Copy(degree, 1, sortedDegree, 0, n);
Array.Sort(sortedDegree);
int[] result = new int[queries.Length];
for (int i = 0; i < queries.Length; i++) {
int query = queries[i];
int count = 0;
// 双指针统计满足 degree[i] + degree[j] > query 的对数
int left = 0, right = n - 1;
while (left < right) {
if (sortedDegree[left] + sortedDegree[right] > query) {
count += right - left;
right--;
} else {
left++;
}
}
// 减去因共享边而不满足条件的对数
foreach (var kvp in shared) {
int u = kvp.Key.Item1, v = kvp.Key.Item2;
int cnt = kvp.Value;
if (degree[u] + degree[v] > query &&
degree[u] + degree[v] - cnt <= query) {
count--;
}
}
result[i] = count;
}
return result;
}
}
var countPairs = function(n, edges, queries) {
const degree = new Array(n + 1).fill(0);
const shared = new Map();
// 计算度数和共享边数
for (const [u, v] of edges) {
degree[u]++;
degree[v]++;
const key = u < v ? `${u},${v}` : `${v},${u}`;
shared.set(key, (shared.get(key) || 0) + 1);
}
// 对度数排序用于双指针
const sortedDegree = degree.slice(1).sort((a, b) => a - b);
const result = [];
for (const query of queries) {
let count = 0;
// 双指针统计满足 degree[i] + degree[j] > query 的对数
let left = 0, right = n - 1;
while (left < right) {
if (sortedDegree[left] + sortedDegree[right] > query) {
count += right - left;
right--;
} else {
left++;
}
}
// 减去因共享边而不满足条件的对数
for (const [key, cnt] of shared) {
const [u, v] = key.split(',').map(Number);
if (degree[u] + degree[v] > query &&
degree[u] + degree[v] - cnt <= query) {
count--;
}
}
result.push(count);
}
return result;
};
复杂度分析
| 复杂度类型 | 大小 |
|---|---|
| 时间复杂度 | O(E + N log N + Q × (N + E)) |
| 空间复杂度 | O(N + E) |
其中 E 为边数，N 为节点数，Q 为查询数。主要时间消耗在排序和对每个查询的双指针扫描以及共享边的检查上。