链接:
1782. 统计点对的数目
题意:
给n个点和m条无向边(可重复),q个查询
定义edge[a]
为一个点是a的边数量,定义ret[a,b]
是edge[a]+edge[b]-(a与b的边)
q个查询q个答案,第i次查询值val[i]
,求所有的1<=a<b<=n
条件下有多少ret[a,b]>val[i]
解:
TLE卡47了
看了评论区用空间换时间,双指针
实际代码:文章来源:https://www.toymoban.com/news/detail-683806.html
class Solution {
public:
typedef pair<int,int> pii;
vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries)
{
vector<int>edgeNum(n+1);//记录edge[a]
map<pii,int>edgePair;
for(auto edge:edges)
{
if(edge[0]>edge[1]) swap(edge[0],edge[1]);
edgeNum[edge[0]]++;
edgeNum[edge[1]]++;
edgePair[{edge[0],edge[1]}]++;//记录(a与b的边)
}
vector<int>ans;
vector<int>edgeNS(edgeNum);
sort(edgeNS.begin(),edgeNS.end());//空间换时间 排序
for(auto querie:queries)
{
int temp=0;
int left=1,right=n;
while(left<right)//双指针
{
if(edgeNS[left] + edgeNS[right] <= querie) left++;
else
{
temp+= right-left;
right--;
}
}
for(auto Pair:edgePair)
{
int s=edgeNum[Pair.first.first]+edgeNum[Pair.first.second];
if(s>querie && s-Pair.second<=querie) temp--;
}
ans.push_back(temp);
}
return ans;
}
};
限制:文章来源地址https://www.toymoban.com/news/detail-683806.html
2 <= n <= 2 * 104
1 <= edges.length <= 105
1 <= ui, vi <= n
ui != vi
1 <= queries.length <= 20
0 <= queries[j] < edges.length
到了这里,关于2023-08-23力扣每日一题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!