C++二分查找：统计点对的数目

本题其它解法

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_vNodeToCountm_vNodeToCount[i]=x，有x条边和i相连
m_vCountsm_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<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<long long, int> m_mEdgeNums;
int m_iN;
};

2023年7月版代码

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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/189747.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

HTTP状态码：如何修复 404 Not Found错误？

HTTP状态码：如何修复 404 Not Found错误？

互联网上各种类型的网站非常多&#xff0c;无论用户还是网站运营者不可避免的会遇到404 Not Found错误&#xff0c;如果遇到404错误&#xff0c;我们应该如何解决呢&#xff1f; 对于用户 检查拼写错误 如果您是遇到错误的用户&#xff0c;请仔细检查 URL 是否有任何拼写错误…
阅读更多...
【Flutter 常见问题系列 第 1 篇】Text组件 文字的对齐、数字和字母对齐中文

【Flutter 常见问题系列 第 1 篇】Text组件 文字的对齐、数字和字母对齐中文

TextStyle中设置height参数即可 对齐的效果 Text的高度 是根据 height 乘于 fontSize 进行计算的、这里指定heiht即可、不指定的会出现 无法对齐的情况&#xff0c;如下&#xff1a; 这种就是无法对齐的情况
阅读更多...
决策树（第四周）

决策树（第四周）

一、决策树基本原理 如下图所示&#xff0c;是一个用来辨别是否是猫的二分类器。输入值有三个&#xff08;x1&#xff0c;x2&#xff0c;x3&#xff09;&#xff08;耳朵形状&#xff0c;脸形状&#xff0c;胡须&#xff09;&#xff0c;其中x1{尖的&#xff0c;圆的}&#xf…
阅读更多...
R语言实现Lasso回归

R语言实现Lasso回归

一、Lasso回归 Lasso 回归&#xff08;Least Absolute Shrinkage and Selection Operator Regression&#xff09;是一种用于线性回归和特征选择的统计方法。它在回归问题中加入了L1正则化项&#xff0c;有助于解决多重共线性&#xff08;多个特征高度相关&#xff09;和特征选…
阅读更多...
什么是轻量应用服务器？可以从亚马逊云科技的优势入手了解

什么是轻量应用服务器？可以从亚马逊云科技的优势入手了解

什么是轻量应用服务器&#xff1f; 随着如今各行各业对云计算的需求越来越多&#xff0c;云服务器也被越来越多的企业所广泛采用。其中&#xff0c;轻量应用服务器是一种简单、高效、可靠的云计算服务&#xff0c;能够为开发人员、企业和个人提供轻量级的虚拟专用服务器&#x…
阅读更多...
【深入剖析K8s】容器技术基础（一）：从进程开始说起

【深入剖析K8s】容器技术基础（一）：从进程开始说起

容器其实是一种特殊的进程而已。 可执行镜像 为了能够让这些代码正常运行’我们往往还要给它提供数据’比如我们这个加法程序所需要的输人文件这些数据加上代码本身的二进制文件放在磁盘上’就是我们平常所说的一个程序,也叫代码的可执行镜像&#xff08;executablejmage&…
阅读更多...
PostgreSQL+patroni+etcd+haproxy+keepalived高可用

PostgreSQL+patroni+etcd+haproxy+keepalived高可用

PostgreSQLpatronietcdhaproxykeepalived 高可用架构 部署环境 部署postgresql-15 一主二从&#xff1a; role主机组件主库 node203 192.168.56.203 pg15.5 Patroni、Etcd&#xff0c;haproxy、keepalived 从库 node204 192.168.56.204 pg15.5 Patroni、Etcd&#xff0c;ha…
阅读更多...
机器人开发的选择

机器人开发的选择

喷涂机器人 码垛机器人 纸箱码垛机器人 焊接机器人 跳舞机器人 管道清理机器人 工地巡检机器人 点餐机器人 化工巡检机器人 装箱机器人 安防巡检机器人 迎宾机器人好像有点像软银那个 污水管道检测机器人 大酒店用扫地机器人 家用扫地机器人 工厂用&#xff08;…
阅读更多...
免费不限字数的文本转语音AI配音工具，无需安装

免费不限字数的文本转语音AI配音工具，无需安装

上周给大家分享了AI绘本故事制作&#xff0c;很多小伙伴让我&#xff0c;推荐一款免费的AI配音&#xff0c;音色质量富有情感语调&#xff0c;而且手机上就能用的文本转语音工具。 OK&#xff0c;那么今天就给小伙伴们推荐一款我经常自用的AI配音工具&#xff0c;无需安装下载&…
阅读更多...
防火墙命令行基础配置实验（H3C模拟器）

防火墙命令行基础配置实验（H3C模拟器）

嘿&#xff0c;这里是目录&#xff01; ⭐ H3C模拟器资源链接1. 实验示意图2. 要求3. 当前配置3.1 PC配置3.2 FW配置&#xff08;防火墙&#xff09;[^7][^8]3.2.1 FW1配置3.2.2 FW2配置 3.3 R配置3.3.1 R1配置3.3.2 R2配置 3.4 SW配置3.4.1 SW1配置3.4.2 SW2配置3.4.3 SW3配置…
阅读更多...
blender 3D眼球结构

blender 3D眼球结构

角膜&#xff08;Cornea&#xff09;&#xff1a;眼球的前部&#xff0c;透明的曲面&#xff0c;负责折射光线。虹膜&#xff08;Iris&#xff09;&#xff1a;眼睛的颜色部分&#xff0c;控制瞳孔大小以调整进入眼睛的光量。瞳孔&#xff08;Pupil&#xff09;&#xff1a;虹膜…
阅读更多...
offer 选择难？说说我的 2 个思考

offer 选择难？说说我的 2 个思考

大家好&#xff0c;我是鱼皮。秋招仍在进行中&#xff0c;随着越来越多的公司开奖&#xff0c;最近 编程导航星球 的小伙伴们也陆续发来了 offer 报喜&#xff1a; 图片 图片 但也有一部分小伙伴陷入了 “甜蜜的烦恼”&#xff0c;拿了几个 offer 却不知道怎么选择。 offer 选择…
阅读更多...
【刷题宝典NO.4】

【刷题宝典NO.4】

目录 公交站间的距离 生命游戏 公交站间的距离 https://leetcode.cn/problems/distance-between-bus-stops/ 环形公交路线上有 n 个站&#xff0c;按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离&#xff0c;distance[i] 表示编号为 i 的车站和编号为 …
阅读更多...
Pure-Pursuit 跟踪五次多项式轨迹

Pure-Pursuit 跟踪五次多项式轨迹

Pure-Pursuit 跟踪五次多项式轨迹 考虑双移线轨迹 X 轴方向位移较大&#xff0c;机械楼停车场长度无法满足 100 ~ 120 m&#xff0c;因此采用五次多项式进行轨迹规划&#xff0c;在轨迹跟踪部分也能水一些内容 调整 double_lane.cpp 为 ref_lane.cpp&#xff0c;结合 FrenetP…
阅读更多...
OpenFeign入门

OpenFeign入门

OpenFeign是Spring Cloud OpenFeign&#xff0c;是Spring Cloud团队开发的基于Feign的框架 1、OpenFeign功能升级 OpenFeign在Feign的基础上提供了以下增强和扩展功能 &#xff08;1&#xff09;便于集成Spring Cloud组件&#xff1a;OpenFeign与Spring Cloud其他组件&#…
阅读更多...
float和double（浮点型数据）在内存中的储存方法

float和double（浮点型数据）在内存中的储存方法

作者&#xff1a;元清加油 主页&#xff1a;主页 编译环境&#xff1a;visual studio 2022 (x86) 相信大家都知道数据在内存中是以二进制储存的 整数的储存方法是首位是符号位&#xff0c;后面便是数值位 那么浮点数在内存中是怎么储存的呢&#xff1f;我们先来看一个例子&am…
阅读更多...
C语言-内存函数详解

C语言-内存函数详解

文章目录 1. memcpy使用和模拟实现2. memmove使用和模拟实现3. memset函数的使用4. memcmp函数的使用 1. memcpy使用和模拟实现 返回类型和参数&#xff1a; void * memcpy ( void * destination, const void * source, size_t num );1.函数memcpy从source的位置开始向后复制…
阅读更多...
叠加原理（superposition principle）、线性系统

叠加原理（superposition principle）、线性系统

叠加原理&#xff08;superposition principle&#xff09;&#xff1a;指对一个系统而言&#xff0c;两个或多个输入产生的输出&#xff0c;等于这几个输入单独引起的输出的和&#xff0c;即输入的叠加等于各输入单独引起的输出的叠加。 线性系统&#xff1a;一个系统&#x…
阅读更多...
Java毕业设计 SpringBoot 车辆充电桩系统

Java毕业设计 SpringBoot 车辆充电桩系统

Java毕业设计 SpringBoot 车辆充电桩系统 SpringBoot 车辆充电桩系统 功能介绍 首页 图片轮播 登录注册 充电桩展示 搜索充电桩 充电桩报修 充电常识 个人中心 我的收藏 后台管理 登录 首页 个人中心 维修员管理 用户管理 电桩类别管理 充电桩管理 充电桩报修管理 维修回复管…
阅读更多...
B树与B+树的对比

B树与B+树的对比

B树&#xff1a; m阶B树的核心特性&#xff1a; 树中每个节点至多有m棵子树&#xff0c;即至多含有m-1个关键字根节点的子树数属于[2, m]&#xff0c;关键字数属于[1, m-1]&#xff0c;其他节点的子树数属于 [ ⌈ m 2 ⌉ , m ] [\lceil \frac{m}{2}\rceil, m] [⌈2m​⌉,m]&am…
阅读更多...
最新文章

Copyright @ 2022~2023