当前位置: 首页 > news >正文

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 &#xff0c;按要求返回一个新数组 counts 。数组 counts 有该性质&#xff1a; counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。 示例 1&#xff1a; 输入&#xff1a;nums [5,2,6,1] 输出&#xff1a;[2,1,1,0] 解释&#xff1a; 5 …...

python类如何实例化对象

python类如何实例化对象 1、把类看作是定制的数据类型。既然是类型&#xff0c;只能用来表示数据的类型&#xff0c;不能直接用来保存数据。**要保存数据&#xff0c;首先需要创建一个类似于这类容器的东西&#xff0c;称为对象(或例子)。通过类别产生对象的过程称为例子。 2、…...

基于GB28181-2022实现web无插件播放H265视频

目前发布的GB28181-2022增加了对前端设备视频H265编码格式的支持&#xff0c;所以实现国标平台通过浏览器对H265视频流的无插件的解码播放将是未来的趋势。 目前大多的方案都是通过平台端把H265转码为H264&#xff0c;再推送到web前端进行解码播放&#xff0c;这种方式因为需要…...

Linux多线程服务端编程:使用muduo C++网络库 学习笔记 第六章 muduo网络库简介

2010年3月作者写了一篇《学之者生&#xff0c;用之者死——ACE历史与简评》&#xff08;http://blog.csdn.net/Solstice/archive/2010/03/10/5364096.aspx&#xff0c;ACE是&#xff08;Adaptive Communication Environment&#xff09;是一个C编写的开源框架&#xff0c;用于开…...

「免费活动」敏捷武林上海站 | 与 Scrum.org CEO 面对面

活动介绍 过去的几年里&#xff0c;外界的风云变幻为我们的生活增添了一些不一样的色彩。在VUCA世界的浪潮里&#xff0c;每一个人都成为自己生活里的冒险家。面对每一次的变化&#xff0c;勇于探索未知&#xff0c;迎接挑战&#xff0c;努力追逐更好的自己。 七月&#xff0…...

深入大模型与ChatGPT

关注微信公众号掌握更多技术动态 --------------------------------------------------------------- 一、大模型原理 1.Transformer (1)求知之路&#xff1a;LLM 学到了什么知识 LLM 从海量自由文本中学习了大量知识&#xff0c;如果把这些知识做粗略分类的话&#xff0c;…...

ubuntu(18.04)中架设HiGlass docker镜像服务,已尝试mcool、bedpe、wig格式文件

前言 使用到的软件 docker 文档 &#xff1a; https://www.docker.com/ HiGlass 文档&#xff1a;http://docs.higlass.io/higlass_docker.html#running-locally https://github.com/higlass/higlass-dockerhiglass-docker 地址&#xff1a;https://github.com/higla…...

通过API和无代码开发,邻医云如何连接电商平台,集成CRM和客服系统

通过API连接电商平台&#xff1a;邻医云的实践 邻医云&#xff0c;一款致力于改变中国医药行业传统经营方式的技术服务产品&#xff0c;用技术的力量帮助实现数字化转型。邻医云已经在零售、仓储物流、互联网医院、工业等各个领域与各大平台进行合作&#xff0c;帮助客户降低成…...

Python selenium元素的定位

视频版教程&#xff1a;一天掌握python爬虫【基础篇】 涵盖 requests、beautifulsoup、selenium 对象的定位应该是自动化测试的核心&#xff0c;要想操作一个对象&#xff0c;首先应该识别这个对象。一个对象就是一个人一样&#xff0c;他 会有各种的特征&#xff08;属性&…...

Android图形系统之HWComposer、ComposerHal、ComposerImpl、Composer、Hwc2::Composer实例总结(十四)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生从来没有捷径,只有行动才是治疗恐惧和懒惰的唯一良药. 更多原创,欢迎关注:Android…...

MASK-RCNN tensorflow环境搭建

此教程默认你已经安装了Anaconda&#xff0c;且tensorflow 为cpu版本。为什么不用gpu版本&#xff0c;原因下面解释。 此教程默认你已经安装了Anaconda。 因为tensorflow2.1后的gpu版&#xff0c;不支持windows。并且只有高版本的tensorflow才对应我的CUDA12.2&#xff1b; 而…...

企业级开发命名规范有哪些?

企业级开发通常会遵循一些命名规范以提高代码的可读性、可维护性和一致性。以下是一些常见的企业级开发命名规范&#xff1a; 1&#xff1a;变量和函数命名&#xff1a; 使用有意义的名称&#xff0c;能够清晰描述变量或函数的用途和功能。使用驼峰命名法&#xff08;camelCa…...

sitespeedio.io 前端页面监控安装部署接入influxdb 到grafana

1.docker部署influxdb,部署1.8一下&#xff0c;不然语法有变化后面用不了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 模块化极速开发框架。模块市场拥有丰富的功能应用&#xff0c;支持后台一键快速安装&#xff0c;让开发者能快的实现业务功能开发。 系统完全开源&#xff0c;基于 Apache 2.0 开源协议&#xff0c;免费且不限制商业使用。 功能特性 丰富的模块市…...

【LVS实战】02 搭建一个LVS-NAT模式实验

一、网络结构 用虚拟机搭建如下的几台机器&#xff0c;并配置如下的ip 关于虚拟机网卡和网络的配置&#xff0c;可以参考 iptables章节&#xff0c;05节&#xff1a;网络转发实验 主机A模拟外网的机器 B为负载均衡的机器 C和D为 RealServer 二、C和D主机的网关设置 C和D机…...

Word 将文档中的【第几条】批量加粗

目录预览 一、问题描述二、解决方案三、参考链接 一、问题描述 我要制作一份文档&#xff0c;关于法律条文的&#xff0c;然后需要将条文中的【第几条】字样进行加粗表示&#xff0c;格式刷是不可能格式刷的&#xff0c;这明显不适合此种批量的操作&#xff0c;浪费事件。所以…...

苹果AirTag固件更新

苹果公司针对其热销的物品追踪器 AirTag 于今天发布了新的固件更新&#xff0c;最新版本号为 2A61&#xff0c;但是这次更新苹果并未提供发布说明&#xff0c;所以目前还不知道这次更新有什么新内容。 关于这次更新&#xff0c;用户无法自己手动更新 AirTag 固件&#xff0c;因…...

04.Oracle的体系架构

Oracle的体系架构 一、主要组件 一、主要组件 下面是一张网图&#xff0c;大家可以了解一下oracle的体系架构 Oracle数据库的体系架构可以分为以下几个主要组件&#xff1a;实例&#xff08;Instance&#xff09;、数据库&#xff08;Database&#xff09;、表空间&#xff…...

01【保姆级】-GO语言特点和安装使用和hello

01-GO语言基本概念和安装使用 一、概念1.1 Go语言的诞生1.2 GO语言的特点&#xff1a; 二、安装go2.1 安装2.2 安装环境变量 三、下载&安装goland3.1 官网下载3.2 下载后&#xff0c;进行安装&#xff1a; 四、编写Hello&#xff08;详解&#xff09; 如何学习&#xff1a;…...

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-…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

手动给中文分词和 直接用神经网络RNN做有什么区别

手动分词和基于神经网络&#xff08;如 RNN&#xff09;的自动分词在原理、实现方式和效果上有显著差异&#xff0c;以下是核心对比&#xff1a; 1. 实现原理对比 对比维度手动分词&#xff08;规则 / 词典驱动&#xff09;神经网络 RNN 分词&#xff08;数据驱动&#xff09…...

可下载旧版app屏蔽更新的app市场

软件介绍 手机用久了&#xff0c;app越来越臃肿&#xff0c;老手机卡顿成常态。这里给大家推荐个改善老手机使用体验的方法&#xff0c;还能帮我们卸载不需要的app。 手机现状 如今的app不断更新&#xff0c;看似在优化&#xff0c;实则内存占用越来越大&#xff0c;对手机性…...