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(nlogn+m)。m的边数。

步骤

每个查询分两步:

一,和a或b相连的边数,严格大于iQue的点对数量。注意,同时和a和b相连算两次,只和a或b相连算一次。

二,枚举各边。如果符合第一步,扣除本边数量后,不再符合题意则减掉。本解法在预处理阶段确保v[0]大于v[1]。

注意:本解题将a和b都减一,这样其范围为:[0,n)。

变量解释

m_vNodeToCount m_vNodeToCount[i]=x,有x条边和i相连
m_vCounts m_vNodeToCount的升序,第一步只考虑和a或b相连的边数,不需要知道a和b的具体值
m_mMaskCount 各边数量,key是a和b的编码,value是数量

代码

核心代码

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)会重复结算
    for (auto left = m_iN - 1; left >= 0 ; left--)
    {   
      iNum += m_vCounts.end() - std::upper_bound(m_vCounts.begin()+left+1, 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::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;
};

测试用例

template <class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template <class T>
void Assert(const vector<T>& v1, const vector<T>& 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<int>> edges;
  vector<int> queries;
  vector<int> 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<int>{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<int>{10, 10, 9, 8, 6});
  }
  //CConsole::Out(res);
}

2023年3月版代码

class Solution {
public:
vector countPairs(int n, vector& 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 = (iMin>=0) ? 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_map m_mEdgeNums;
int m_iN;
};

2023年7月版代码

class Solution {
public:
vector countPairs(int n, vector& 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_map 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


相关文章
|
6月前
|
算法 C++
【动态规划】【子序列除重】【C++算法】1987不同的好子序列数目
【动态规划】【子序列除重】【C++算法】1987不同的好子序列数目
|
6月前
|
算法 测试技术 C++
【动态规划】【C++算法】2518. 好分区的数目
【动态规划】【C++算法】2518. 好分区的数目
|
6月前
|
人工智能 移动开发 算法
【动态规划】【C++算法】LeetCoce996正方形数组的数目
【动态规划】【C++算法】LeetCoce996正方形数组的数目
|
6月前
|
算法 测试技术 C++
【动态规划】【图论】【C++算法】1575统计所有可行路径
【动态规划】【图论】【C++算法】1575统计所有可行路径
|
6月前
|
人工智能 算法 测试技术
【动态规划】【二分查找】C++算法 466 统计重复个数
【动态规划】【二分查找】C++算法 466 统计重复个数
|
4月前
|
NoSQL Redis C++
c++开发redis module问题之在复杂的Redis模块中,特别是使用第三方库或C++开发时,接管内存统计有哪些困难
c++开发redis module问题之在复杂的Redis模块中,特别是使用第三方库或C++开发时,接管内存统计有哪些困难
|
4月前
|
C++
1456. 定长子串中元音的最大数目C++
1456. 定长子串中元音的最大数目C++
|
6月前
|
C++
41.用c++编写程序:从键盘上任意输20个1-99之间的整数,分别统计其个位数0-9的数字各有多少
41.用c++编写程序:从键盘上任意输20个1-99之间的整数,分别统计其个位数0-9的数字各有多少
50 0
|
6月前
|
算法 测试技术 Serverless
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
|
6月前
|
算法 测试技术 C#
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II