统计点对的数目【LC1782】
给你一个无向图，无向图由整数
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个查询的答案。请注意，图中可能会有 重复边 。
先统计再剔除非法，降低时间复杂度！
- 思路：哈希表+枚举+差分【超时】
使用哈希表统计每个点的度数，以及每条边的出现次数，然后枚举统计每个点对的cnt，两个点的度数之和减这条边出现次数 - 实现
class Solution { public int[] countPairs(int n, int[][] edges, int[] queries) { Map<Integer,Integer> map = new HashMap<>();// 记录边数及数目 int m = edges.length; int[] countEdges = new int[n + 1];// 每个点的边数 int[] d = new int[m + 2];// 边数大于等于i的对数 for (int[] edge : edges){ int u = edge[0] - 1, v = edge[1] - 1; if (u > v){ int tmp = u; u = v; v = tmp; } countEdges[u]++; countEdges[v]++; map.put(u * n + v, map.getOrDefault(u * n + v, 0) + 1); } for (int i = 0; i < n; i++){ for (int j = i + 1; j < n; j++){ int a = map.getOrDefault(i * n + j, 0); int count = countEdges[i] + countEdges[j] - a; d[0]++; d[count]--; } } for (int i = 1; i <= m; i++){ d[i] += d[i - 1]; } int[] res = new int[queries.length]; for (int i = 0; i < queries.length; i++){ res[i] = d[queries[i]]; } return res; } }
class Solution { public int[] countPairs(int n, int[][] edges, int[] queries) { // deg[i] 表示与点 i 相连的边的数目 var deg = new int[n + 1]; // 节点编号从 1 到 n var cntE = new HashMap<Integer, Integer>(); for (var 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; } deg[x]++; deg[y]++; // 统计每条边的出现次数 // 用一个 int 存储两个不超过 65535 的数 cntE.merge(x << 16 | y, 1, Integer::sum); // cntE[x<<16|y]++ } var ans = new int[queries.length]; var sortedDeg = deg.clone(); Arrays.sort(sortedDeg); // 排序，为了双指针 for (int j = 0; j < queries.length; j++) { int q = queries[j]; int left = 1, right = n; // 相向双指针 while (left < right) { if (sortedDeg[left] + sortedDeg[right] <= q) { left++; } else { ans[j] += right - left; right--; } } for (var e : cntE.entrySet()) { int k = e.getKey(), c = e.getValue(); int s = deg[k >> 16] + deg[k & 0xffff]; // 取出 k 的高 16 位和低 16 位 if (s > q && s - c <= q) { ans[j]--; } } } return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/count-pairs-of-nodes/solutions/2400682/ji-bai-100cong-shuang-zhi-zhen-dao-zhong-yhze/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution { public int[] countPairs(int n, int[][] edges, int[] queries) { var deg = new int[n + 1]; var cntE = new HashMap<Integer, Integer>(); for (var e : edges) { int x = e[0], y = e[1]; if (x > y) { int tmp = x; x = y; y = tmp; } deg[x]++; deg[y]++; cntE.merge(x << 16 | y, 1, Integer::sum); } // 统计 deg 中元素的出现次数 var cntDeg = new HashMap<Integer, Integer>(); int maxDeg = 0; for (int i = 1; i <= n; i++) { cntDeg.merge(deg[i], 1, Integer::sum); // cntDeg[deg[i]]++ maxDeg = Math.max(maxDeg, deg[i]); } // 2) var cnts = new int[maxDeg * 2 + 2]; for (var e1 : cntDeg.entrySet()) { int deg1 = e1.getKey(), c1 = e1.getValue(); for (var e2 : cntDeg.entrySet()) { int deg2 = e2.getKey(), c2 = e2.getValue(); if (deg1 < deg2) cnts[deg1 + deg2] += c1 * c2; else if (deg1 == deg2) cnts[deg1 + deg2] += c1 * (c1 - 1) / 2; } } // 3) for (var e : cntE.entrySet()) { int k = e.getKey(), c = e.getValue(); int s = deg[k >> 16] + deg[k & 0xffff]; cnts[s]--; cnts[s - c]++; } // 4) 计算 cnts 的后缀和 for (int i = cnts.length - 1; i > 0; i--) cnts[i - 1] += cnts[i]; for (int i = 0; i < queries.length; i++) queries[i] = cnts[Math.min(queries[i] + 1, cnts.length - 1)]; return queries; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/count-pairs-of-nodes/solutions/2400682/ji-bai-100cong-shuang-zhi-zhen-dao-zhong-yhze/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
