自助贸易免费建站,公司项目推广有什么方式,网站建设用户量分析,济南建设网站平台本题其它解法
C双指针算法#xff1a;统计点对的数目
本周推荐阅读
C二分算法#xff1a;得到子序列的最少操作次数
本文涉及的基础知识点
二分查找算法合集
题目
给你一个无向图#xff0c;无向图由整数 n #xff0c;表示图中节点的数目#xff0c;和 edges 组成…本题其它解法
C双指针算法统计点对的数目
本周推荐阅读
C二分算法得到子序列的最少操作次数
本文涉及的基础知识点
二分查找算法合集
题目
给你一个无向图无向图由整数 n 表示图中节点的数目和 edges 组成其中 edges[i] [ui, vi] 表示 ui 和 vi 之间有一条无向边。同时给你一个代表查询的整数数组 queries 。 第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目 a b cnt 是与 a 或者 b 相连的边的数目且 cnt 严格大于 queries[j] 。 请你返回一个数组 answers 其中 answers.length queries.length 且 answers[j] 是第 j 个查询的答案。 请注意图中可能会有 多重边 。 示例 1 输入n 4, edges [[1,2],[2,4],[1,3],[2,3],[2,1]], queries [2,3] 输出[6,5]
解释每个点对中与至少一个点相连的边的数目如上图所示。 answers[0] 6。所有的点对(a, b)中边数和都大于2故有6个 answers[1] 5。所有的点对(a, b)中除了(3,4)边数等于3其它点对边数和都大于3故有5个。 示例 2 输入n 5, edges [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries [1,2,3,4,5] 输出[10,10,9,8,6] 参数范围 2 n 2 * 104 1 edges.length 105 1 ui, vi n ui ! vi 1 queries.length 20 0 queries[j] edges.length
分析
时间复杂度
每个查询的时间复杂度是O(nlognm)。m的边数。
步骤
每个查询分两步 一和a或b相连的边数严格大于iQue的点对数量。注意同时和a和b相连算两次只和a或b相连算一次。 二枚举各边。如果符合第一步扣除本边数量后不再符合题意则减掉。本解法在预处理阶段确保v[0]大于v[1]。 注意:本解题将a和b都减一这样其范围为[0,n)。
变量解释
m_vNodeToCountm_vNodeToCount[i]x有x条边和i相连m_vCountsm_vNodeToCount的升序,第一步只考虑和a或b相连的边数不需要知道a和b的具体值m_mMaskCount各边数量key是a和b的编码value是数量
代码
核心代码
class Solution {
public:vectorint countPairs(int n, vectorvectorint edges, vectorint queries) { m_iN n;m_vNodeToCount.resize(n);for (auto v : edges){if (v[0] v[1]){swap(v[0], v[1]);}v[0]--;v[1]--; m_vNodeToCount[v[0]];m_vNodeToCount[v[1]];m_mMaskCount[Mask(v[0], v[1])];}m_vCounts m_vNodeToCount;sort(m_vCounts.begin(), m_vCounts.end());vectorint vRet;for (const auto que : queries){vRet.emplace_back(Query(que));}return vRet;}int Query(int iQue)const{int iNum 0;// 包括a或b的边数大于iQue的数量(a,b)和(b,a)会重复结算for (auto left m_iN - 1; left 0 ; left--){ iNum m_vCounts.end() - std::upper_bound(m_vCounts.begin()left1, m_vCounts.end(),iQue-m_vCounts[left]);}//扣处重复数量for (const auto [iMask, iNum1] : m_mMaskCount){auto [a, b] Parse(iMask);const int tmp m_vNodeToCount[a] m_vNodeToCount[b] - iQue;if (tmp 0 ){if (tmp iNum1){iNum--;}}} return iNum;}int Mask(int a, int b){return a * m_iUnit b;}std::pairint,int Parse(const int iMask)const{return std::make_pair(iMask / m_iUnit, iMask % m_iUnit);}const int m_iUnit 1000 * 100;unordered_mapint, int m_mMaskCount;vectorint m_vNodeToCount;vectorint m_vCounts;int m_iN;
};测试用例
template class T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}template class T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}
}int main()
{int n;vectorvectorint edges;vectorint queries;vectorint res;{ n 4;edges { {1,2},{2,4},{1,3},{2,3},{2,1} };queries { 2,3 };Solution slu;res slu.countPairs(n, edges, queries);Assert(res, vectorint{6, 5});}{n 5;edges { {1,5},{1,5},{3,4},{2,5},{1,3},{5,1},{2,3},{2,5} };queries { 1,2,3,4,5 };Solution slu;res slu.countPairs(n, edges, queries);Assert(res, vectorint{10, 10, 9, 8, 6});}//CConsole::Out(res);
}2023年3月版代码
class Solution { public: vector countPairs(int n, vectorvector edges, vector queries) { m_vDeg.resize(n 1); m_iN n; for (const auto v : edges) { m_vDeg[v[0]]; m_vDeg[v[1]]; m_mEdgeNums[min(v[0], v[1])m_llMul max(v[0], v[1])]; } vector vRet; for (const auto q : queries) { vRet.push_back(Query1(q) - Query2(q)); } return vRet; } long long Query1(int iQuery) { CTreeArr tree(1000100 1); long long iRet 0; for (int i 1; i m_iN; i) { const int iMin iQuery - m_vDeg[i]; const int iLessEqualNum (iMin0) ? tree.Sum(iMin ) : 0; iRet (i - 1) - iLessEqualNum; tree.Add(m_vDeg[i],1); } return iRet; } long long Query2(int iQuery) { long long llSub 0; for (auto it : m_mEdgeNums) { const int iNum1 m_vDeg[it.first%m_llMul] m_vDeg[it.first/m_llMul]; if (iNum1 iQuery) { continue; } if (iNum1 - it.second iQuery) { llSub; } } return llSub; } long long m_llMul 1000 * 100; vector m_vDeg; std::unordered_maplong long, int m_mEdgeNums; int m_iN; };
2023年7月版代码
class Solution { public: vector countPairs(int n, vectorvector edges, vector queries) { m_vConnectNums.resize(n 1); m_n n; for (const auto v : edges) { m_vConnectNums[v[0]]; m_vConnectNums[v[1]]; m_mEdgeMaskNum[ToMask(v)]; } m_iMaxSize *std::max_element(m_vConnectNums.begin(), m_vConnectNums.end()); vector vRet; for (const auto que : queries) { vRet.emplace_back(Query(que)); } return vRet; } int Query(const int iQuery) { CTreeArr treeArr(m_iMaxSize 1); int iRet 0; for (int i 1; i m_n; i) { const int iCurSize m_vConnectNums[i]; int iMin iQuery - iCurSize; if (iMin 0) { iRet (i - 1); } else if (iMin m_iMaxSize) { } else { const int iSum1 treeArr.Sum(m_iMaxSize); const int iSum2 treeArr.Sum(iMin); iRet iSum1 - iSum2; } treeArr.Add(iCurSize, 1); } for (const auto it : m_mEdgeMaskNum) { const int iNum m_vConnectNums[it.first / 100000] m_vConnectNums[it.first % 100000]; if (iNum iQuery) { continue; } if (iNum - it.second iQuery) { iRet–; } } return iRet; } int ToMask(const vector v) { return min(v[0], v[1]) * 100000 max(v[0], v[1]); } std::unordered_mapint, int m_mEdgeMaskNum; vector m_vConnectNums; int m_n; int m_iMaxSize; };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
