网站项目建设计划,西宁软件网站建设,西安市建设银行网站,源码分享平台2023-08-23每日一题
一、题目编号
1782. 统计点对的数目二、题目链接
点击跳转到题目位置
三、题目描述
给你一个无向图#xff0c;无向图由整数 n #xff0c;表示图中节点的数目#xff0c;和 edges 组成#xff0c;其中 edges[i] [ui, vi] 表示 ui 和 vi 之间有一…2023-08-23每日一题
一、题目编号
1782. 统计点对的数目二、题目链接
点击跳转到题目位置
三、题目描述
给你一个无向图无向图由整数 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 个查询的答案。
请注意图中可能会有 重复边 。
示例 1 示例 2 提示
2 n 2 * 1041 edges.length 1051 ui, vi nui ! vi1 queries.length 200 queries[j] edges.length
四、解题代码
class Solution {unordered_mapint, int cnt;int find(int left, int right, vectorint 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;}vectorint countPairs(int n, vectorvectorint edges, vectorint queries) {vectorint 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];}vectorint arr degree;vectorint 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) 最后返回结果数组即可。
