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-…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...
客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践
01技术背景与业务挑战 某短视频点播企业深耕国内用户市场,但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大,传统架构已较难满足当前企业发展的需求,企业面临着三重挑战: ① 业务:国内用户访问海外服…...
