本周推荐阅读
本题其它解法
题目
给你一个无向图，无向图由整数 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(n+m)。m是边数。
只优化了每个查询的第一步
m_vCounts[x]和m_vCounts[left]都严格大于iQue，x的取值范围是的左开右开空间(right,n)。
为了不重复计算，我们要确保left <=right，也就是：
if (right < left) { right = left; }
代码
核心代码
class Solution { public: vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& 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()); vector<int> 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)会重复结算 int right = m_iN - 1; for (auto left = 0 ; left < m_iN ; left++ ) { if (right < left) { right = left; } while ((right > left) && (m_vCounts[left] + m_vCounts[right] > iQue)) { right--; } iNum += m_iN - right - 1; } //扣处重复数量 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::pair<int,int> Parse(const int iMask)const { return std::make_pair(iMask / m_iUnit, iMask % m_iUnit); } const int m_iUnit = 1000 * 100; unordered_map<int, int> m_mMaskCount; vector<int> m_vNodeToCount; vector<int> m_vCounts; int m_iN; };
测试用例
class Solution { public: vector countPairs(int n, vector<vector>& edges, vector& 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()); vector 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)会重复结算 int right = m_iN - 1; for (auto left = 0 ; left < m_iN ; left++ ) { if (right < left) { right = left; } while ((right > left) && (m_vCounts[left] + m_vCounts[right] > iQue)) { right–; } iNum += m_iN - right - 1; } //扣处重复数量 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::pair<int,int> Parse(const int iMask)const { return std::make_pair(iMask / m_iUnit, iMask % m_iUnit); } const int m_iUnit = 1000 * 100; unordered_map<int, int> m_mMaskCount; vector m_vNodeToCount; vector m_vCounts; int m_iN; }; template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& 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; vector<vector> edges; vector queries; vector 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, vector{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, vector{10, 10, 9, 8, 6}); }
//CConsole::Out(res);
}
小的优化
双指针先反向，再相同方向。其实同向就可以提前退出了。
if (right < left) { iNum += (m_iN - left-1) * (m_iN - left) / 2; break; }
class Solution { public: vector countPairs(int n, vector<vector>& edges, vector& 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()); vector 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)会重复结算 int right = m_iN - 1; for (auto left = 0 ; left < m_iN ; left++ ) { if (right < left) { iNum += (m_iN - left-1) * (m_iN - left) / 2; break; } while ((right > left) && (m_vCounts[left] + m_vCounts[right] > iQue)) { right–; } iNum += m_iN - right - 1; } //扣处重复数量 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::pair<int,int> Parse(const int iMask)const { return std::make_pair(iMask / m_iUnit, iMask % m_iUnit); } const int m_iUnit = 1000 * 100; unordered_map<int, int> m_mMaskCount; vector m_vNodeToCount; vector m_vCounts; int m_iN; };
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
