What is the main approach for solving 'Count Pairs Of Nodes'?

The main approach is to precompute node degrees, use hash tables for counting pairs, and then efficiently process queries based on these precomputed values.

How can I optimize the solution for large graphs in 'Count Pairs Of Nodes'?

Optimization is achieved by precomputing node degrees and using hash lookups to avoid recalculating degree sums for each query, which ensures the solution scales well.

What common mistakes should I avoid in the 'Count Pairs Of Nodes' problem?

Avoid brute force pair counting and ensure that your solution handles edge cases, such as nodes with no edges or high-density connections.

How does the graph structure affect the solution for 'Count Pairs Of Nodes'?

The graph's structure impacts the number of node pairs considered and the degree calculations. Efficient handling of dense graphs and sparse graphs is crucial for optimal performance.

What are some variations of the 'Count Pairs Of Nodes' problem?

Variants include changing the threshold in queries, handling directed graphs, or returning the top N node pairs based on degree sums.

#1782

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计点对的数目

给你一个无向图，无向图由整数 n ，表示图中节点的数目，和 edges 组成，其中 edges[i] = [u i , v i ] 表示 u i 和 v i 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目： a c…

数组哈希表双指针二分查找图

题目描述

给你一个无向图，无向图由整数 n ，表示图中节点的数目，和 edges 组成，其中 edges[i] = [u_i, v_i] 表示 u_i 和 v_i之间有一条无向边。同时给你一个代表查询的整数数组 queries 。

第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目：

a < b
cnt 是与 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 * 10⁴
1 <= edges.length <= 10⁵
1 <= u_i, v_i <= n
u_i!= v_i
1 <= queries.length <= 20
0 <= queries[j] < edges.length

lightbulb

解题思路

方法一：哈希表 + 排序 + 二分查找

根据题目，我们可以知道，与点对 $(a, b)$ 相连的边数等于“与 $a$ 相连的边数”加上“与 $b$ 相连的边数”，再减去同时与 $a$ 和 $b$ 相连的边数。

因此，我们可以先用数组 $cnt$ 统计与每个点相连的边数，用哈希表 $g$ 统计每个点对的数量。

然后，对于每个查询 $q$ ，我们可以枚举 $a$ ，对于每个 $a$ ，我们可以通过二分查找找到第一个满足 $cnt[a] + cnt[b] > q$ 的 $b$ ，先将数量累加到当前查询的答案中，然后减去一部分重复的边。

时间复杂度 $O(q \times (n \times \log n + m))$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别是点数和边数，而 $q$ 是查询数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def countPairs(
        self, n: int, edges: List[List[int]], queries: List[int]
    ) -> List[int]:
        cnt = [0] * n
        g = defaultdict(int)
        for a, b in edges:
            a, b = a - 1, b - 1
            a, b = min(a, b), max(a, b)
            cnt[a] += 1
            cnt[b] += 1
            g[(a, b)] += 1

        s = sorted(cnt)
        ans = [0] * len(queries)
        for i, t in enumerate(queries):
            for j, x in enumerate(s):
                k = bisect_right(s, t - x, lo=j + 1)
                ans[i] += n - k
            for (a, b), v in g.items():
                if cnt[a] + cnt[b] > t and cnt[a] + cnt[b] - v <= t:
                    ans[i] -= 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate efficiently uses hash tables to avoid recalculating pair degrees multiple times.
question_mark
The solution scales well to larger graphs by leveraging precomputation and optimized queries.
question_mark
The candidate understands how to handle edge cases, such as nodes with no edges or densely connected nodes.

warning

常见陷阱

外企场景

error
Not handling graphs with nodes that have no edges, leading to incorrect degree calculations.
error
Using brute force to calculate pairs for each query, which may lead to performance issues for large graphs.
error
Misunderstanding how to efficiently use hash tables, which could result in unnecessary recomputation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The problem can be modified by changing the threshold in each query, making it more dynamic.
arrow_right_alt
You could add a variation where the graph is directed, affecting how incident pairs are calculated.
arrow_right_alt
Another variant might involve returning the top N node pairs based on the degree sum for each query.

help

常见问题

外企场景

继续练习

#3186 施咒的最大总伤害 #1346 检查整数及其两倍数是否存在 #923 三数之和的多种可能