2023-08-23每日一题

一、题目编号

1782. 统计点对的数目

二、题目链接

点击跳转到题目位置

三、题目描述

给你一个无向图，无向图由整数 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：

示例 2：

提示：

• 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

四、解题代码

class Solution {unordered_map<int, int> cnt;int find(int left, int right, vector<int>& arr, int num){int ans = -1; while(left <= right){int mid = ((right - left) >> 1) + left;if(arr[mid] > num){ans = mid;right = mid - 1;                } else{left = mid + 1; }}return ans;}public:void swap(int &x, int &y){int temp = x;x = y;y = temp;}vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {vector<int> degree(n);for(int i = 0; i < edges.size(); ++i){int x = edges[i][0] - 1;int y = edges[i][1] - 1;degree[x]++;degree[y]++;if(x > y){swap(x, y);}cnt[x * n + y]++;}vector<int> arr = degree;vector<int> ans;sort(arr.begin(), arr.end());        for(int i = 0; i < queries.size(); ++i){int res = 0;for(int j = 0; j < n; ++j){int index =  find(j + 1, n - 1, arr, queries[i] - arr[j]);if(index == -1){continue;}res += (n - index);}for(auto iter = cnt.begin(); iter != cnt.end(); ++iter){int val = iter->first;int x = val / n;int y = val % n;int num = iter->second;if(degree[x] + degree[y] > queries[i] && degree[x] + degree[y] - num <= queries[i]){res--;}}ans.push_back(res);}return ans;}
};

五、解题思路

(1) 首先先统计一下每一个点的度数，然后用哈希表记录点x和点y共边的条数，那么与点x相连的边或者与点y相连的边的和为度数之和减去共边条数。

(2) 然后将度数在放在一个新的数组arr中，并且从小到大排序。

(3) 为了方便计算，将点的下标由1 ~ n改变成0 ~ n - 1。

(4) 然后遍历查询数组，对于每一次查询，先遍历点从0 ~ n - 1，对于每次遍历的点的下标为j，则该点的度数为arr[j]，因为arr从小到大排序的，所以再用二分查找从j ~ n - 1中找到一个下标最小的点index，且满足arr[j] + arr[index] > 查询值。那么此时数对的数量为n - index，加上即可。

(5) 最后不要忘记减去共边的情况。如果度数之和满足条件但是减去共边之后不满足条件，就需要剔除。

(6) 最后返回结果数组即可。