C++归并排序算法的应用:计算右侧小于当前元素的个数
题目
给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例 1:
输入:nums = [5,2,6,1]
输出:[2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
示例 2:
输入:nums = [-1]
输出:[0]
示例 3:
输入:nums = [-1,-1]
输出:[0,0]
参数范围
1 <= nums.length <= 105
-104 <= nums[i] <= 104
2023年3月版
用的树状数组
template
class CTreeArr
{
public:
CTreeArr(int iSize) :m_vData(iSize+1)
{
}
void Add(int index, T value)
{
index++;
while (index < m_vData.size())
{
m_vData[index] += value;
index += index&(-index);
}
}
T Sum(int index)
{
index++;
T ret = 0;
while (index )
{
ret += m_vData[index];
index -= index&(-index);
}
return ret;
}
private:
vector m_vData;
};
class Solution {
public:
vector countSmaller(vector& nums) {
int iMin = *std::min_element(nums.begin(), nums.end());
for (auto& n : nums)
{
n -= iMin;
}
int iMax = *std::max_element(nums.begin(), nums.end());
CTreeArr treeArr(iMax + 1);
vector vRet(nums.size());
for (int i = nums.size() - 1; i >= 0; i–)
{
vRet[i] = treeArr.Sum(nums[i] - 1);
treeArr.Add(nums[i],1);
}
return vRet;
}
};
2023年8月 归并排序
class CMergeSortIndex
{
public:
CMergeSortIndex(const vector& nums):m_nums(nums)
{
m_c = nums.size();
m_vIndexs.resize(nums.size());
iota(m_vIndexs.begin(), m_vIndexs.end(), 0);
}
void SortIndex( int left, int right)
{
if (right - left <= 1)
{
return;
}
const int mid = left + (right - left) / 2;
SortIndex( left, mid);
SortIndex( mid, right);
//nums的[left,mid) 和[mid,right)分别排序
vector vIndexs;
int i1 = left, i2 = mid;
while ((i1 < mid) && (i2 < right))
{
if (m_nums[m_vIndexs[i1]] > m_nums[m_vIndexs[i2]])
{
vIndexs.emplace_back(m_vIndexs[i2++]);
}
else
{
vIndexs.emplace_back(m_vIndexs[i1]);
OnAdd1(i1++, i2, left, mid, right);
}
}
while (i1 < mid)
{
vIndexs.emplace_back(m_vIndexs[i1]);
OnAdd1(i1++, i2, left, mid, right);
}
while (i2 < right)
{
vIndexs.emplace_back(m_vIndexs[i2++]);
}
for (int i = 0; i < vIndexs.size(); i++)
{
m_vIndexs[i + left] = vIndexs[i];
}
}
vector Sort()
{
SortIndex(0, m_c);
vector vRet(m_c);
for (int i = 0; i < m_c; i++)
{
vRet[i] = m_nums[m_vIndexs[i]];
}
return vRet;
}
protected:
virtual void OnAdd1(int i1, int i2, int left, int mid, int right) = 0;
int m_c;
const vector& m_nums;
vector m_vIndexs;
};
class CCountSmalle : public CMergeSortIndex
{
public:
CCountSmalle(const vector& nums):CMergeSortIndex(nums)
{
m_vRet.resize(m_c);
}
vector m_vRet;
// 通过 CMergeSortIndex 继承
virtual void OnAdd1(int i1, int i2, int left, int mid, int right) override
{m_vRet[m_vIndexs[i1]] += i2 - mid;
}
};
class Solution {
public:
vector countSmaller(vector& nums) {
CCountSmalle test(nums);
auto tmp = test.Sort();
return test.m_vRet;
}
};
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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
| 鄙人想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
| 墨家名称的来源:有所得以墨记之。 |
| 如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17

相关文章:
C++归并排序算法的应用:计算右侧小于当前元素的个数
题目 给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。 示例 1: 输入:nums [5,2,6,1] 输出:[2,1,1,0] 解释: 5 …...
python类如何实例化对象
python类如何实例化对象 1、把类看作是定制的数据类型。既然是类型,只能用来表示数据的类型,不能直接用来保存数据。**要保存数据,首先需要创建一个类似于这类容器的东西,称为对象(或例子)。通过类别产生对象的过程称为例子。 2、…...
基于GB28181-2022实现web无插件播放H265视频
目前发布的GB28181-2022增加了对前端设备视频H265编码格式的支持,所以实现国标平台通过浏览器对H265视频流的无插件的解码播放将是未来的趋势。 目前大多的方案都是通过平台端把H265转码为H264,再推送到web前端进行解码播放,这种方式因为需要…...
Linux多线程服务端编程:使用muduo C++网络库 学习笔记 第六章 muduo网络库简介
2010年3月作者写了一篇《学之者生,用之者死——ACE历史与简评》(http://blog.csdn.net/Solstice/archive/2010/03/10/5364096.aspx,ACE是(Adaptive Communication Environment)是一个C编写的开源框架,用于开…...
「免费活动」敏捷武林上海站 | 与 Scrum.org CEO 面对面
活动介绍 过去的几年里,外界的风云变幻为我们的生活增添了一些不一样的色彩。在VUCA世界的浪潮里,每一个人都成为自己生活里的冒险家。面对每一次的变化,勇于探索未知,迎接挑战,努力追逐更好的自己。 七月࿰…...
深入大模型与ChatGPT
关注微信公众号掌握更多技术动态 --------------------------------------------------------------- 一、大模型原理 1.Transformer (1)求知之路:LLM 学到了什么知识 LLM 从海量自由文本中学习了大量知识,如果把这些知识做粗略分类的话,…...
ubuntu(18.04)中架设HiGlass docker镜像服务,已尝试mcool、bedpe、wig格式文件
前言 使用到的软件 docker 文档 : https://www.docker.com/ HiGlass 文档:http://docs.higlass.io/higlass_docker.html#running-locally https://github.com/higlass/higlass-dockerhiglass-docker 地址:https://github.com/higla…...
通过API和无代码开发,邻医云如何连接电商平台,集成CRM和客服系统
通过API连接电商平台:邻医云的实践 邻医云,一款致力于改变中国医药行业传统经营方式的技术服务产品,用技术的力量帮助实现数字化转型。邻医云已经在零售、仓储物流、互联网医院、工业等各个领域与各大平台进行合作,帮助客户降低成…...
Python selenium元素的定位
视频版教程:一天掌握python爬虫【基础篇】 涵盖 requests、beautifulsoup、selenium 对象的定位应该是自动化测试的核心,要想操作一个对象,首先应该识别这个对象。一个对象就是一个人一样,他 会有各种的特征(属性&…...
Android图形系统之HWComposer、ComposerHal、ComposerImpl、Composer、Hwc2::Composer实例总结(十四)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只有行动才是治疗恐惧和懒惰的唯一良药. 更多原创,欢迎关注:Android…...
MASK-RCNN tensorflow环境搭建
此教程默认你已经安装了Anaconda,且tensorflow 为cpu版本。为什么不用gpu版本,原因下面解释。 此教程默认你已经安装了Anaconda。 因为tensorflow2.1后的gpu版,不支持windows。并且只有高版本的tensorflow才对应我的CUDA12.2; 而…...
企业级开发命名规范有哪些?
企业级开发通常会遵循一些命名规范以提高代码的可读性、可维护性和一致性。以下是一些常见的企业级开发命名规范: 1:变量和函数命名: 使用有意义的名称,能够清晰描述变量或函数的用途和功能。使用驼峰命名法(camelCa…...
sitespeedio.io 前端页面监控安装部署接入influxdb 到grafana
1.docker部署influxdb,部署1.8一下,不然语法有变化后面用不了grafana模板 docker run -d -p 8086:8086 --name influxdb -v $PWD/influxdb-data:/var/lib/influxdb influxdb:1.7.11-alpine docker exec -it influxdb_id bash #influx create user admin with pass…...
ModStartCMS v7.5.0 内外网映射节流,安全使用增强
ModStart 是一个基于 Laravel 模块化极速开发框架。模块市场拥有丰富的功能应用,支持后台一键快速安装,让开发者能快的实现业务功能开发。 系统完全开源,基于 Apache 2.0 开源协议,免费且不限制商业使用。 功能特性 丰富的模块市…...
【LVS实战】02 搭建一个LVS-NAT模式实验
一、网络结构 用虚拟机搭建如下的几台机器,并配置如下的ip 关于虚拟机网卡和网络的配置,可以参考 iptables章节,05节:网络转发实验 主机A模拟外网的机器 B为负载均衡的机器 C和D为 RealServer 二、C和D主机的网关设置 C和D机…...
Word 将文档中的【第几条】批量加粗
目录预览 一、问题描述二、解决方案三、参考链接 一、问题描述 我要制作一份文档,关于法律条文的,然后需要将条文中的【第几条】字样进行加粗表示,格式刷是不可能格式刷的,这明显不适合此种批量的操作,浪费事件。所以…...
苹果AirTag固件更新
苹果公司针对其热销的物品追踪器 AirTag 于今天发布了新的固件更新,最新版本号为 2A61,但是这次更新苹果并未提供发布说明,所以目前还不知道这次更新有什么新内容。 关于这次更新,用户无法自己手动更新 AirTag 固件,因…...
04.Oracle的体系架构
Oracle的体系架构 一、主要组件 一、主要组件 下面是一张网图,大家可以了解一下oracle的体系架构 Oracle数据库的体系架构可以分为以下几个主要组件:实例(Instance)、数据库(Database)、表空间ÿ…...
01【保姆级】-GO语言特点和安装使用和hello
01-GO语言基本概念和安装使用 一、概念1.1 Go语言的诞生1.2 GO语言的特点: 二、安装go2.1 安装2.2 安装环境变量 三、下载&安装goland3.1 官网下载3.2 下载后,进行安装: 四、编写Hello(详解) 如何学习:…...
EVM6678L 开发教程: IBL-TFTP 引导 elf 文件
目录 EVM6678L 开发教程: IBL-TFTP 引导 elf 文件安装 Tftpd64测试工程测试说明 EVM6678L 开发教程: IBL-TFTP 引导 elf 文件 参考: "C:\ti\mcsdk_2_01_02_06\tools\boot_loader\examples\i2c\tftp\docs\README.txt" 此教程介绍如何在 EVM6678L 开发板上实现 IBL-…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
