【C++算法】49.分治_归并_计算右侧小于当前元素的个数
文章目录
- 题目链接:
- 题目描述:
- 解法
- C++ 算法代码:
- 图解
题目链接:
315. 计算右侧小于当前元素的个数
题目描述:
解法
归并排序(分治)
当前元素的后面,有多少个比我小。(降序)
C++ 算法代码:
class Solution
{vector<int> ret; // 存储结果:每个元素右侧小于当前元素的个数vector<int> index; // 记录 nums 中当前元素的原始下标,用于追踪元素位置int tmpNums[500010]; // 临时数组,用于归并排序中合并两个子数组int tmpIndex[500010]; // 临时数组,用于保存合并后的索引顺序
public:vector<int> countSmaller(vector<int>& nums) {int n = nums.size();ret.resize(n); // 初始化结果数组大小,默认值都是0index.resize(n); // 初始化索引数组大小// 初始化索引数组,记录每个元素的原始位置for(int i = 0; i < n; i++)index[i] = i;mergeSort(nums, 0, n - 1); // 对整个数组进行归并排序return ret; // 返回结果数组}void mergeSort(vector<int>& nums, int left, int right){if(left >= right) return; // 基本情况:如果区间只有一个元素或为空,则直接返回// 1. 根据中间元素,划分区间int mid = (left + right) >> 1; // 计算中间位置,相当于 (left + right) / 2// 2. 递归地处理左右两部分mergeSort(nums, left, mid); // 排序左半部分mergeSort(nums, mid + 1, right); // 排序右半部分// 3. 合并两个有序子数组,同时计算右侧小于当前元素的个数int cur1 = left, cur2 = mid + 1, i = 0; // cur1指向左子数组,cur2指向右子数组,i遍历辅助数组while(cur1 <= mid && cur2 <= right) // 当两个子数组都还有元素时{if(nums[cur1] <= nums[cur2]) // 如果左子数组当前元素小于等于右子数组当前元素{tmpNums[i] = nums[cur2]; // 将右子数组的元素放入临时数组tmpIndex[i++] = index[cur2++]; // 同时记录对应的原始索引}else // 如果左子数组当前元素大于右子数组当前元素{// 核心逻辑:此时右子数组中从cur2到right的所有元素都小于当前的nums[cur1]ret[index[cur1]] += right - cur2 + 1; // 将这些元素的数量累加到结果中tmpNums[i] = nums[cur1]; // 将左子数组的元素放入临时数组tmpIndex[i++] = index[cur1++]; // 同时记录对应的原始索引}}// 4. 处理剩余元素while(cur1 <= mid) // 处理左子数组中剩余的元素{tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}while(cur2 <= right) // 处理右子数组中剩余的元素{tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}// 5. 将临时数组中的元素复制回原数组for(int j = left; j <= right; j++){nums[j] = tmpNums[j - left]; // 更新原数组中的元素值index[j] = tmpIndex[j - left]; // 更新原数组中元素对应的原始索引}}
};
图解
例如:nums = [5, 2, 6, 1]
-
初始化:
-
ret = [0, 0, 0, 0]
(结果数组,初始全为0) -
index = [0, 1, 2, 3]
(原始索引数组)
-
-
第一次划分:
- 将
[5, 2, 6, 1]
分为[5, 2]
和[6, 1]
- 将
-
处理左半部分
[5, 2]
:-
进一步划分为
[5]
和[2]
-
这些是单个元素,不再划分
-
合并
[5]
和[2]
(降序合并):- 比较 5 和 2,5 > 2,
nums[cur1] > nums[cur2]
ret[index[cur1]] += right - cur2 + 1;
- 因为左边元素大,所以选择左边元素,
ret
不变 - 合并后,左半部分变为
[5, 2]
,索引变为[0, 1]
- 比较 5 和 2,5 > 2,
-
-
处理右半部分
[6, 1]
:-
进一步划分为
[6]
和[1]
-
这些是单个元素,不再划分
-
合并
[6]
和[1]
(降序合并):- 比较 6 和 1,6 > 1
- 因为左边元素大,所以选择左边元素,
ret
不变 - 合并后,右半部分变为
[6, 1]
,索引变为[2, 3]
-
-
最后合并
[5, 2]
和[6, 1]
(降序合并):- 比较 5 和 6: 5 <= 6,选择右侧元素6,
ret
不变 - 比较 5 和 1: 5 > 1,这时右子数组中只有1比5小,所以
ret[index[cur1]] += right - cur2 + 1 → ret[0] += 3 - 3 + 1 → ret[0] = 1
- 比较 2 和 1: 2 > 1,右子数组中只有1比2小,所以
ret[index[cur1]] += right - cur2 + 1 →ret[1] += 3 - 3 + 1 → ret[1] = 1
- 比较 5 和 6: 5 <= 6,选择右侧元素6,
-
最终结果:
ret = [2, 1, 1, 0]
3.第一次循环:while(cur1 <= mid && cur2 <= right)
4.第二次循环:while(cur1 <= mid && cur2 <= right)
5.第三次循环:while(cur1 <= mid && cur2 <= right)
6.处理剩余元素while(cur2 <= right)
相关文章:
【C++算法】49.分治_归并_计算右侧小于当前元素的个数
文章目录 题目链接:题目描述:解法C 算法代码:图解 题目链接: 315. 计算右侧小于当前元素的个数 题目描述: 解法 归并排序(分治) 当前元素的后面,有多少个比我小。(降序&…...
Multi-class N-pair Loss论文理解
一、N-pair loss 对比 Triplet loss 对于N-pair loss来说,当N2时,与triplet loss是很相似的。对anchor-positive pair,都只有一个negative sample。而且,N-pair loss(N2时)为triplet loss的平滑近似Softpl…...
uniapp微信小程序地图marker自定义气泡 customCallout偶尔显示不全解决办法
这个天坑问题,在微信开发工具上是不会显示出来的,只有在真机上才会偶尔出现随机样式偏移/裁剪/宽长偏移,询问社区也只是让你提交代码片段,并无解决办法。 一开始我怀疑是地图组件加载出现了问题,于是给地图加了一个v-if"reL…...
蓝桥杯嵌入式总结
1.lcd显示和led引脚冲突 在lcd使用到的函数中加入两行代码 uint16_t temp GPIOC->ODR; GPIOC->ODR temp; 2.关于PA15,PB4pwm波输入捕获 首先pwm输入捕获中断 使用 HAL_TIM_IC_Start_IT(&htim2,TIM_CHANNEL_1); 再在输入捕获中断回调函数中使用 void HAL…...
C#的反射机制
C#反射机制详解 什么是反射? 反射(Reflection)是C#中的一项强大功能,它允许程序在运行时动态获取类型信息、访问和操作对象成员。简单来说,反射使程序可以在不预先知道类型的情况下,查看、使用和修改程序集中的代码。 常见反射…...
Java并发编程高频面试题
一、基础概念 1. 并行与并发的区别? 并行:多个任务在多个CPU核心上同时执行(物理上同时)。并发:多个任务在单CPU核心上交替执行(逻辑上同时)。类比:并行是多个窗口同时服务&#x…...
Invalid bound statement (not found)
前言: 通过实践而发现真理,又通过实践而证实真理和发展真理。从感性认识而能动地发展到理性认识,又从理性认识而能动地指导革命实践,改造主观世界和客观世界。实践、认识、再实践、再认识,这种形式,循环往…...
【Vue-路由】学习笔记
目录 <<回到导览路由1.单页应用和多页面2.路由基本使用2.1.路由的含义2.2.VueRouter插件2.3.配置路由规则和导航2.4.组件目录存放2.5.路由模块封装 3.rounter3.1.router-link实现高亮3.2.自定义匹配类名3.3.声明式导航3.3.1.查询参数传参3.3.2.动态路由传参3.3.3.总结 3.…...
前端服务配置详解:从入门到实战
前端服务配置详解:从入门到实战 一、环境配置文件(.env) 1.1 基础结构 在项目根目录创建 .env 文件: # 开发环境 VUE_APP_API_BASE_URL http://localhost:3000/api VUE_APP_VERSION 1.0.0# 生产环境(.env.produc…...
Java安全管理器 - SecurityManager
什么是Java安全管理器? Java安全管理器是Java提供的保护JVM和程序安全的机制,它能限制用户的代码对文件、内存、资源、网络的操作和访问,防止恶意代码入侵程序。常用来控制用户提交的代码对各种资源的访问权限,防止用户恶意提交代…...
Arrays操作工具 Lambda表达式 集合 迭代器 数据结构 泛型 set集合 list集合
Arrays操作工具 自己定义的排序规则 简单理解如果是:o1 - o2 升序排列 o2 - o1 降序排列 Lambda表达式 函数式编程 函数式编程(Functional programming)是一种思想特点。 面向对象:先去找对象,让对象做事情。。函数式…...
ORM、Mybatis和Hibernate、Mybatis使用教程、parameterType、resultType、级联查询案例、resultMap映射
DAY21.1 Java核心基础 ORM Object Relationship Mapping 对象关系映射 面向对象的程序到—关系型数据库的映射 比如java – MySQL的映射 ORM框架就是实现这个映射的框架 Hibernate、Mybatis、MybatisPlus、Spring Data JPA、Spring JDBC Spring Data JPA的底层就是Hiber…...
《Java八股文の文艺复兴》第十一篇:量子永生架构——对象池的混沌边缘(终极试炼·完全体)
Tags: - Java高并发 - 量子架构 - 混沌工程 - 赛博修真 - 三体防御 目录: 卷首语:蝴蝶振翅引发的量子海啸 第一章:混沌初开——对象池的量子涅槃(深度扩展) 第二章:混沌计算——对象复活的降维打击&…...
蓝桥杯备赛---真题训练之15届蓝桥杯找回连接之旅
题目 介绍 在网络世界中,突然间失去了所有的连接。作为勇敢的冒险者,你将踏上一段惊险刺激的旅程,穿越充满谜题和挑战的网络景观,与神秘的网络幽灵对抗,解开断网之谜,找回失去的连接,带领人们重…...
PowerApps MDA-模版-文档模版无法下载和上传Word模版
Power Apps的高级设置-模版中,文档模版目前只能看到新建和上传Excel模版,看不到Word模版 这是一个已知bug, 什么时候能修复不好说,解决办法也很简单,先上传一个Excel模版,随便任何一个实体就行,为的是视图列…...
全国大学生数学建模竞赛赛题深度分析报告(2010-2024)
全国大学生数学建模竞赛赛题深度分析报告(2010-2024) 全国大学生数学建模竞赛(CUMCM)是中国最具影响力的大学生科技竞赛之一,本报告将对2010-2024年间的赛题进行全面统计分析,包括题目类型、领域分布、模型方法等多个维度&#x…...
职坐标解析自动驾驶技术发展新趋势
内容概要 作为智能交通革命的核心驱动力,自动驾驶技术正以惊人的速度重塑出行生态。2023年,行业在多传感器融合与AI算法优化两大领域实现突破性进展:激光雷达、摄像头与毫米波雷达的协同精度提升至厘米级,而深度学习模型的实时决…...
快速入手-前后端分离Python权限系统 基于Django5+DRF+Vue3.2+Element Plus+Jwt
引用:打造前后端分离Python权限系统 基于Django5DRFVue3.2Element PlusJwt 视频教程 (火爆连载更新中..)_哔哩哔哩_bibili 说明:1、结合个人DRF基础和该视频去根据自己的项目进行开发。 2、引用该视频中作者的思路去升华自身的项…...
HTTP 协议详解
HTTP 协议 HTTP(HyperText Transfer Protocol,超文本传输协议)是互联网上应用最广泛的协议之一,用于在客户端(如浏览器)和服务器之间传输超文本(如网页)。 HTTP 是万维网ÿ…...
巧记英语四级单词 Unit1-4【晓艳老师版】
tain—take拿着、sus 下面,只有sur表示上面、ob表示方向、de往下,分开 retain v.保持 re-重复,tain—take拿着,重复的拿着maintain v. 维持,维修,保养 main主要的,主要的东西都拿着的那个人维…...
Transformers without Normalization论文翻译
论文信息: 作者:Jiachen Zhu, Xinlei Chen, Kaiming He, Yann LeCun, Zhuang Liu 论文地址:arxiv.org/pdf/2503.10622 代码仓库:jiachenzhu/DyT: Code release for DynamicTanh (DyT) 摘要 归一化层在现代神经网络中无处不在…...
Ollama
目录 定义与核心功能应用场景Ollama与Llama的关系安装与使用 Ollama是一个开源的本地大语言模型(LLM)运行框架,专为在本地机器上便捷部署和运行大型语言模型而设计。以下是关于Ollama的全面介绍: 定义与核心功能 多种预训练语言模…...
社交app圈子模块0到1实现
一、逻辑分析 用户相关 用户需要能够创建圈子,这涉及到用户身份验证,确保只有注册用户可以进行创建操作。每个圈子有创建者,创建者对圈子有一定的管理权限,如设置圈子规则、邀请成员等。 圈子信息 圈子需要有名称、简介、头像等基…...
OpenCV--图像边缘检测
在计算机视觉和图像处理领域,边缘检测是极为关键的技术。边缘作为图像中像素值发生急剧变化的区域,承载了图像的重要结构信息,在物体识别、图像分割、目标跟踪等众多应用场景中发挥着核心作用。OpenCV 作为强大的计算机视觉库,提供…...
批量压缩 jpg/png 等格式照片|批量调整图片的宽高尺寸
图片格式种类非常的多,并且不同的图片由于像素、尺寸不一样,可能占用的空间也会不一样。文件太大会占用较多的磁盘空间,传输及上传系统都非常不方便,可能会收到限制,因此我们经常会碰到需要对图片进行压缩的需求。如何…...
[Linux系统编程]多线程
多线程 1. 线程1.1 线程的概念1.2 进程与线程对比1.3 轻量级进程 2. Linux线程控制2.1 POSIX 线程(pthread)2.2 线程ID、pthread_t、和进程地址空间的关系2.2.1 pthread_self2.2.2 pthread_create2.2.3 pthread_join2.2.4 线程终止的三种方式2.2.5 pthre…...
进程状态(运行 阻塞 僵尸)及其场景分析
【Linux学习笔记】Linux基本指令及其分析 🔥个人主页:大白的编程日记 🔥专栏:Linux学习笔记 前言 哈喽,各位小伙伴大家好!上期我们讲了进程PCB 今天我们讲的是进程状态(运行 阻塞 僵尸)及其场景分析。话不多说&#…...
程序化广告行业(67/89):DMP系统标签制作与人群拓展深度解析
程序化广告行业(67/89):DMP系统标签制作与人群拓展深度解析 大家好!在之前的分享中,我们对程序化广告的多个关键环节进行了探讨。今天,咱们继续深入了解程序化广告中的DMP系统,聚焦于标签制作和…...
【QT】QPixmap QImage QBitmap QPicture
文章目录 **1. QPixmap****特点****典型应用场景****示例** **2. QImage****特点****典型应用场景****示例** **3. QBitmap****特点****示例** **4. 三者的主要区别****5. 如何选择?****使用 QPixmap 的情况****使用 QImage 的情况****使用 QBitmap 的情况** **6. 相…...
如何开通google Free Tier长期免费云服务器(1C/1G)
Google宣布的一项政策,为标准层级的网络提供每地域200G的免费流量。两项政策结合,于是便可以得到一台1核心、1G内存、30G磁盘、200G流量的小云服务器,可玩性大大提高。这篇文章就分享一下如何正确开机,避免产生额外的费用。 免费…...
Kaggle房价预测
实战 Kaggle 比赛:预测房价 这里李沐老师讲的比较的细致,我根据提供的代码汇总了一下: import hashlib import os import tarfile import zipfile import requests import numpy as np import pandas as pd import torch from matplotlib i…...
4.7学习总结 java集合进阶
集合进阶 泛型 //没有泛型的时候,集合如何存储数据 //结论: //如果我们没有给集合指定类型,默认认为所有的数据类型都是object类型 //此时可以往集合添加任意的数据类型。 //带来一个坏处:我们在获取数据的时候,无法使用他的特有行为。 //此…...
设计模式 - 代理模式Proxy
设计思想: 举个通俗的例子,你想找某局长帮你做一件事情,但局长官位显赫,你又不能轻易见着,你就想到了找他的秘书,通过她传话给局长,这样你就等于请他的秘书帮你办成了那件事。秘书为什么就可以…...
计算机网络体系结构(一)
1.计算机网络概述 1.1计算机网络的概念 计算机网络是由相互连接的计算机及其周边设备构成的系统,这些计算机和设备通过各种通信介质实现数据和资源的共享。计算机网络的主要目的是为了增强信息传递的效率、便利性和可靠性。以下是一些计算机网络的关键概念…...
数据结构与算法-数学-基础数学2(扩展欧几里得算法,组合数问题)
六:扩展欧几里得算法 同余: 若 a≡b(modm),则 m 整除 a−b,即 abkm(k 为整数)。 扩展欧几里得算法 扩展欧几里得算法可用于求解 axbygcd(a,b) 的一组整数解。 #include <iostream> using namesp…...
【力扣hot100题】(072)柱状图中的最大矩阵
这绝对是我做过印象最深的算法题之一。(还有是那道盛水最多的贪心题) 当初不知道想了多少个日日夜夜,所幸这道题已经深深的烙印在了我的脑海里。 现在看来也没那么可怕()不过初见确实非常难想到单调栈。 方法如下&a…...
T-SQL语言的压力测试
T-SQL语言的压力测试 随着数据驱动技术的发展,数据库在现代应用中的角色愈加重要。而在数据库管理系统中,微软的SQL Server凭借其强大的功能和易用性,广泛应用于各行业。在这一环境中,T-SQL(Transact-SQL)…...
debian 系统gnome怎么关闭触摸屏三指滑动
ubuntu如何限制三指手势操作_ubuntu 手势-CSDN博客 参考方案给上面了, kiosk模式 就是专用模式,类似于广告机、售货机那种。 方案 在 Debian 系统的 GNOME 桌面环境中,可以通过以下方法关闭触摸屏三指滑动功能: 安装 gnome-tweaks 工具:...
【9】搭建k8s集群系列(二进制部署)之安装work-node节点组件(kube-proxy)和网络组件calico
承接上一篇文章,继续安装工作节点的第二个组件:kube-proxy 一、创建配置文件 cat > /opt/kubernetes/cfg/kube-proxy.conf << EOF KUBE_PROXY_OPTS"--logtostderrfalse \\ --v2 \\ --log-dir/opt/kubernetes/logs \\ --config/opt/kubern…...
MongoDB及Yapi迁移数据
一、MongoDB安装及迁移 1、导入MongoDB GPG密钥 sudo rpm --import https://www.mongodb.org/static/pgp/server-5.0.asc 2、创建MongoDB 安装源配置文件 vi /etc/yum.repos.d/mongodb-org-5.0.repo,添加以下内容: [mongodb-org-5.0] nameMongoDB Repo…...
高效解读机器语言,profinet转ethernet ip网关烟草企业自动化升级案例分析
工业通信协议转换在烟草生产线的实践应用 某中型烟草生产企业为提高自动化水平,引进了西门子S7-1500系列PLC控制系统和防爆型科氏力质量流量计。但在系统集成阶段,技术人员发现PLC支持的PROFINET协议与流量计采用的EtherNet/IP协议存在互操作障碍&#x…...
使用Scade实现神经网络算法
在ERTS2022中,ANSYS 发表了使用Scade实现神经网络AI算法的相关工作。论文题目为《Programming Neural Networks Inference in a Safety-Critical Simulation-based Framework》 背景与挑战 神经网络在安全关键系统中的应用:随着嵌入式系统中自主性的引入…...
rom定制系列------小米10pro机型定制解锁固件 原生安卓15批量线刷固件 操作解析与界面预览
注意;固件用于自己机型忘记密码或者手机号注销等出现设备锁 过保修期 售后无视的机型,勿用于非法途径 目前有粉丝联系,自己的机型由于手机号注销导致手机更新系统后出现设备锁界面。另外也没有解锁bl。目前无法使用手机。经过询问是小米10pro机型。根据…...
2023年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析
2023年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析 全国大学生数学建模竞赛(China Undergraduate Mathematical Contest in Modeling)是国家教委高教司和中国工业与应用数学学会共同主办的面向全国大学生的群众性科技活动,目的在于激…...
2014年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析
2014年-全国大学生数学建模竞赛(CUMCM)试题速浏、分类及浅析 全国大学生数学建模竞赛(China Undergraduate Mathematical Contest in Modeling)是国家教委高教司和中国工业与应用数学学会共同主办的面向全国大学生的群众性科技活动,目的在于激励学生学习数学的积极性,提高学…...
【Docker基础】--查阅笔记1
目录 Docker是什么Docker解决什么问题Docker的理念Docker基本组成镜像(image)容器(container)仓库(registry) Docker平台架构Docker基本实现原理 Docker常用命令总结 Docker是什么 Docker解决什么问题 统…...
算法(动态规划)
动态规划 基本思想 将问题分解为相互重叠的子问题 定义子问题:将原问题分解为若干个子问题。确定状态转移方程:找到子问题之间的递推关系。边界条件:确定初始状态的值。递推计算:根据状态转移方程和边界条件逐步计算子问题的解。…...
2025 年前端与后端开发方向的抉择与展望-优雅草卓伊凡
2025 年前端与后端开发方向的抉择与展望-优雅草卓伊凡 在 2025 年这个科技浪潮奔涌的时代,软件开发领域持续变革,前端与后端开发方向的抉择,成为众多从业者和爱好者亟待破解的关键命题。卓伊凡就频繁收到这样的疑问:“2025 年了&…...
指纹浏览器技术架构解析:高并发批量注册业务的工程化实践——基于分布式指纹引擎与防关联策略的深度实现
一、技术背景与行业痛点 在跨境电商、广告投放、问卷调查等场景中,批量注册与多账号矩阵运营已成为刚需。然而,主流平台(如亚马逊、Facebook、Google)的风控系统通过浏览器指纹追踪(Canvas/WebGL/WebRTC等)…...
基于SpringBoot的“智慧医疗采购系统”的设计与实现(源码+数据库+文档+PPT)
基于SpringBoot的“智慧医疗采购系统”的设计与实现(源码数据库文档PPT) 开发语言:Java 数据库:MySQL 技术:SpringBoot 工具:IDEA/Ecilpse、Navicat、Maven 系统展示 系统总体结构图 局部E-R图 系统首页界面 系统…...