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

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

酒店预订订房小程序源码系统 带完整搭建教程

酒店预订订房小程序源码系统是一种基于互联网技术的线上预订平台&#xff0c;旨在为用户提供方便快捷的酒店预订服务。该系统通常包括前端用户界面、后端服务器和数据库三个部分&#xff0c;其中前端界面主要展示酒店信息、订房需求信息、订单信息等&#xff0c;后端服务器负责…

当函数参数为一级指针,二级指针

当函数参数为一级指针&#xff0c;二级指针 在讲述内容之前&#xff0c;先讲四点重要知识 1.当传入参数时&#xff0c;函数形参会立即申请形参的内存空间&#xff0c;函数执行完毕后&#xff0c;形参的内存空间立即释放掉。 1.指针是存放其他变量地址的变量。指针有自己的内…

Spring Boot Web MVC

文章目录 一、Spring Boot Web MVC 概念二、状态码三、其他注解四、响应操作 一、Spring Boot Web MVC 概念 Spring Web MVC 是⼀个 Web 框架&#xff0c;一开始就包含在Spring 框架里。 1. MVC 定义 软件⼯程中的⼀种软件架构设计模式&#xff0c;它把软件系统分为模型、视…

uniapp实现路线规划

UniApp是一个基于Vue.js框架开发的跨平台应用开发框架&#xff0c;可以同时构建iOS、Android、H5等多个平台的应用。它使用了基于前端技术栈的Web开发方式&#xff0c;通过编写一套代码&#xff0c;即可在不同平台上运行和发布应用。 UniApp具有以下特点&#xff1a; 跨平台开…

【设计模式】第8节:结构型模式之“适配器模式”

一、简介 适配器模式是用来做适配的&#xff0c;它将不兼容的接口转换为可兼容的接口&#xff0c;让原本由于接口不兼容而不能一起工作的类可以一起工作。 适配器模式角色&#xff1a; 请求者client&#xff1a;调用服务的角色目标Target&#xff1a;定义了Client要使用的功…

Window下coturn服务器的搭建

Window下搭建coturn服务器&#xff1a; 准备材料&#xff1a; 1、安装Cygwin&#xff0c;地址&#xff1a;https://cygwin.com/install.html 由于Window无法直接部署coturn&#xff0c;因此需要下载安装Cygwin在Window上部署Linux虚拟环境。 在安装的时候需要安装几下packe…

Azure机器学习 - 使用与Azure集成的Visual Studio Code实战教程

本文介绍如何启动远程连接到 Azure 机器学习计算实例的 Visual Studio Code。 借助 Azure 机器学习资源的强大功能&#xff0c;使用 VS Code 作为集成开发环境 (IDE)。 在VS Code中将计算实例设置为远程 Jupyter Notebook 服务器。 关注TechLead&#xff0c;分享AI全维度知识。…

目标检测 图像处理 计算机视觉 工业视觉

目标检测 图像处理 计算机视觉 工业视觉 工业表盘自动识别&#xff08;指针型和数值型&#xff09;智能水尺识别电梯中电动车识别&#xff0c;人数统计缺陷检测&#xff08;半导体&#xff0c;电子元器件等&#xff09;没带头盔检测基于dlib的人脸识别抽烟检测和睡岗检测/驾驶疲…

Java选择与循环

1.选择 前言&#xff1a;什么是选择呢&#xff1f;在我们的人生中处处面临着选择&#xff0c;比如说在学校你可以选择玩&#xff0c;摆烂&#xff0c;当然也可以选择努力写代码&#xff0c;刷题。什么样的选择就会面临什么样的结果。 其实程序和人生一样&#xff1a;顺序中夹杂…

大数据技术之集群数据迁移

文章目录 数据治理之集群迁移数据 数据治理之集群迁移数据 准备两套集群&#xff0c;我这使用apache集群和CDH集群。 启动集群 启动完毕后&#xff0c;将apache集群中&#xff0c;hive库里dwd,dws,ads三个库的数据迁移到CDH集群 在apache集群里hosts加上CDH Namenode对应域名并…

IPv4首部格式

IPv4首部格式 IPv4数据报的首部格式及其内容是实现IPv4协议各种功能的基础。 在TCPIP标准中&#xff0c;各种数据格式常常以32比特(即4字节)为单位来描述。 IPv4首部格式图 ## IPv4数据报的组成 主要由固定部分(20字节)可变部分(最大40字节) - 固定部分是指每个IPv4数据报都必…

Java使用pdfbox进行pdf和图片之间的转换

简介 pdfbox是Apache开源的一个项目,支持pdf文档操作功能。 官网地址: Apache PDFBox | A Java PDF Library 支持的功能如下图.引入依赖 <dependency><groupId>org.apache.pdfbox</groupId><artifactId>pdfbox-app</artifactId><version>…

去除短视频平台水印 | 一键下载神器

当咱们这些视频创作者在短视频平台找素材的时候&#xff0c;经常会碰到下载下来居然带着平台水印的烦恼&#xff0c;这可让咱们的创作受到了限制和困扰不过别着急&#xff01;咱这就推荐几款超方便的短视频一键去水印下载工具&#xff0c;帮你快速去掉水印&#xff0c;轻松搞定…

你没有见过的 git log 风格

背景 git大家都不陌生&#xff0c;git log 也是大家经常用的指令&#xff0c;今天分享三种 git log的美化格式&#xff0c;大家看看哪种更易读。 git log -15 --graph --decorate --oneline 带有 pretty 格式的git log 风格 log --color --graph --prettyformat:‘%Cred%h%C…

生态扩展:Flink Doris Connector

生态扩展&#xff1a;Flink Doris Connector 官网地址&#xff1a; https://doris.apache.org/zh-CN/docs/dev/ecosystem/flink-doris-connector flink的安装&#xff1a; tar -zxvf flink-1.16.0-bin-scala_2.12.tgz mv flink-1.16.0-bin-scala_2.12.tgz /opt/flinkflink环境…

华为防火墙 配置 SSLVPN

需求&#xff1a; 公司域环境&#xff0c;大陆客户端居家办公室需要连到公司域&#xff0c;这里可以在上海防火墙上面开通SSLVPN&#xff0c;员工就可以透过SSLVPN连通上海公司的内网&#xff0c;但是由于公司域控有2个站点&#xff0c;一个在上海&#xff0c;一个在台北&…

【2023年MathorCup高校数学建模挑战赛-大数据竞赛】赛道A:基于计算机视觉的坑洼道路检测和识别 python 代码解析

【2023年MathorCup高校数学建模挑战赛-大数据竞赛】赛道A&#xff1a;基于计算机视觉的坑洼道路检测和识别 python 代码解析 1 题目 坑洼道路检测和识别是一种计算机视觉任务&#xff0c;旨在通过数字图像&#xff08;通常是地表坑洼图像&#xff09;识别出存在坑洼的道路。这…

框架安全-CVE 复现Apache ShiroApache Solr漏洞复现

文章目录 服务攻防-框架安全&CVE 复现&Apache Shiro&Apache Solr漏洞复现中间件列表常见开发框架Apache Shiro-组件框架安全暴露的安全问题漏洞复现Apache Shiro认证绕过漏洞&#xff08;CVE-2020-1957&#xff09;CVE-2020-11989验证绕过漏洞CVE_2016_4437 Shiro-…

分享者 - 携程旅游创作者搬砖项目图文教程

大家好&#xff01;携程这个出行旅游平台相信大家都不陌生吧。 每天都有大量的旅客在里面浏览攻略&#xff0c;寻找灵感和旅游建议。 那么&#xff0c;我们的项目就是把一些优质的小红书平台上的旅游攻略或作品&#xff0c;经过处理后搬运到携程平台上发布。 这个项目如何操作呢…

06_es分布式搜索引擎2

一、DSL查询文档 1.DSL查询分类 ①查询所有&#xff1a;match_all ②全文检索&#xff1a;利用分词器对用户输入的内容分词&#xff0c;倒排索引去匹配 match_query multi_match_query ③精确查询&#xff1a;根据精确词条查找数据&#xff0c;查找的是keyword,数值,日期,b…