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-…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
2025-05-08-deepseek本地化部署
title: 2025-05-08-deepseek 本地化部署 tags: 深度学习 程序开发 2025-05-08-deepseek 本地化部署 参考博客 本地部署 DeepSeek:小白也能轻松搞定! 如何给本地部署的 DeepSeek 投喂数据,让他更懂你 [实验目的]:理解系统架构与原…...
背包问题双雄:01 背包与完全背包详解(Java 实现)
一、背包问题概述 背包问题是动态规划领域的经典问题,其核心在于如何在有限容量的背包中选择物品,使得总价值最大化。根据物品选择规则的不同,主要分为两类: 01 背包:每件物品最多选 1 次(选或不选&#…...
ZYNQ学习记录FPGA(二)Verilog语言
一、Verilog简介 1.1 HDL(Hardware Description language) 在解释HDL之前,先来了解一下数字系统设计的流程:逻辑设计 -> 电路实现 -> 系统验证。 逻辑设计又称前端,在这个过程中就需要用到HDL,正文…...
Springboot 高校报修与互助平台小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,高校报修与互助平台小程序被用户普遍使用,为…...
