LC.P1782[统计点对的数目]

方法一：排序+双指针+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int[] countPairs(int n, int[][] edges, int[] queries) {
        // degree[i] 表示与点 i 相连的边的数目
        int[] degree = new int[n + 1]; // 节点编号从 1 到 n
        Map<Integer, Integer> cntE = new HashMap<>();
        for (int[] e : edges) {
            int x = e[0], y = e[1];
            if (x > y) {
                // 交换 x 和 y，因为 1-2 和 2-1 算同一条边
                int tmp = x;
                x = y;
                y = tmp;
            }
            ++degree[x];
            ++degree[y];
            // 统计每条边的出现次数
            // 用一个 int 存储两个不超过 65535 的数
            cntE.merge(x << 16 | y, 1, Integer::sum); // cntE[x<<16|y]++
        }

        int[] ans = new int[queries.length];
        int[] sortedDegree = degree.clone();
        Arrays.sort(sortedDegree); // 排序，为了双指针
        for (int j = 0; j < queries.length; ++j) {
            int q = queries[j];
            int left = 1, right = n;
            while (left < right) {
                if (sortedDegree[left] + sortedDegree[right] <= q) {
                    ++left;
                } else {
                    ans[j] += right - left;
                    --right;
                }
            }
            for (Map.Entry<Integer, Integer> e : cntE.entrySet()) {
                int k = e.getKey(), c = e.getValue();
                int s = degree[k >> 16] + degree[k & 0xffff]; // 取出 k 的高 16 位和低 16 位
                if (s > q && s - c <= q) {
                    --ans[j];
                }
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(nlogn + q(n + m))$，其中 $m$ 为 $edges$ 的长度，$q$ 为 $queries$ 的长度
  • 空间复杂度：$O(n + m)$