LeetCode-315. Count of Smaller Numbers After Self
目录
题目描述
解题思路
【C++】
【Java】
复杂度分析
LeetCode-315. Count of Smaller Numbers After Self
https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/
题目描述
Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].
Example 1:
Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.
Example 2:
Input: nums = [-1] Output: [0]
Example 3:
Input: nums = [-1,-1] Output: [0,0]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104
解题思路
【C++】
class Solution {
private:vector<int> index{};vector<int> tmpIndex{};vector<int> ans{};void merge(vector<int>& nums, int start, int mid, int end) {int p1 = start, p2 = mid + 1, cur = start, len = end - start + 1;while (p1 <= mid && p2 <= end) {if (nums[index[p1]] > nums[index[p2]]) {ans[index[p1]] += end - p2 + 1;tmpIndex[cur++] = index[p1++];} else {tmpIndex[cur++] = index[p2++];}}while (p1 <= mid) {tmpIndex[cur++] = index[p1++];}while (p2 <= end) {tmpIndex[cur++] = index[p2++];}for (int i = start; i <= end; i++) {index[i] = tmpIndex[i];}}void mergeSort(vector<int>& nums, int start, int end) {if (start < end) {int mid = start + (end - start) / 2;mergeSort(nums, start, mid);mergeSort(nums, mid + 1, end);merge(nums, start, mid, end);}}public:vector<int> countSmaller(vector<int>& nums) {index.resize(nums.size());tmpIndex.resize(nums.size());ans.resize(nums.size(), 0);for (int i = 0; i < nums.size(); i++) {index[i] = i;}mergeSort(nums, 0, nums.size() - 1);return ans;}
};
【Java】
class Solution {private int[] index;private int[] tmpIndex;private List<Integer> ans;private void merge(int[] nums, int start, int mid, int end) {int p1 = start, p2 = mid + 1, cur = start, len = end - start + 1;while (p1 <= mid && p2 <= end) {if (nums[index[p1]] > nums[index[p2]]) {ans.set(index[p1], ans.get(index[p1]) + end - p2 + 1);tmpIndex[cur++] = index[p1++];} else {tmpIndex[cur++] = index[p2++];}}while (p1 <= mid) {tmpIndex[cur++] = index[p1++];}while (p2 <= end) {tmpIndex[cur++] = index[p2++];}for (int i = start; i <= end; i++) {index[i] = tmpIndex[i];}}private void mergeSort(int[] nums, int start, int end) {if (start < end) {int mid = start + (end - start) / 2;mergeSort(nums, start, mid);mergeSort(nums, mid + 1, end);merge(nums, start, mid, end);}}public List<Integer> countSmaller(int[] nums) {index = new int[nums.length];tmpIndex = new int[nums.length];ans = new ArrayList<Integer>(nums.length);for (int i = 0; i < nums.length; i++) {index[i] = i;ans.add(0);}mergeSort(nums, 0, nums.length - 1);return ans;}
}
复杂度分析
- 时间复杂度:O(nlogn),即归并排序的时间复杂度。
- 空间复杂度:O(n),这里归并排序的下标映射数组、临时下标映射数组以及答案数组的空间代价均为 O(n)。
- 注意:不建议在merge函数内创建临时下标映射数组,那样做会反复申请和销毁资源,消耗较大。
相关文章:
LeetCode-315. Count of Smaller Numbers After Self
目录 题目描述 解题思路 【C】 【Java】 复杂度分析 LeetCode-315. Count of Smaller Numbers After Selfhttps://leetcode.com/problems/count-of-smaller-numbers-after-self/description/ 题目描述 Given an integer array nums, return an integer array counts whe…...
根据导数的定义计算导函数
根据导数的定义计算导函数 1. Finding derivatives using the definition (使用定义求导)1.1. **We want to differentiate f ( x ) 1 / x f(x) 1/x f(x)1/x with respect to x x x**</font>1.2. **We want to differentiate f ( x ) x f(x) \sqrt{x} f(x)x wi…...
WPF关于打开新窗口获取数据的回调方法的两种方式
一种基于消息发送模式 一种基于回调机制 基于消息发送模式 父页面定义接收的_selectedPnNumberStandarMsg保证是唯一 Messenger.Default.Register<PlateReplaceApplyModel>(this, _selectedPnNumberStandarMsgToken, platePnNumberModel > { …...
复杂网络(四)
一、规则网络 孤立节点网络全局耦合网络(又称完全网络)星型网络一维环二维晶格 编程实践: import networkx as nx import matplotlib.pyplot as pltn 10 #创建孤立节点图 G1 nx.Graph() G1.add_nodes_from(list(range(n))) plt.figure(f…...
用MATLAB符号工具建立机器人的动力学模型
目录 介绍代码功能演示拉格朗日方法回顾求解符号表达式数值求解 介绍 开发机器人过程中经常需要用牛顿-拉格朗日法建立机器人的动力学模型,表示为二阶微分方程组。本文以一个二杆系统为例,介绍如何用MATLAB符号工具得到微分方程表达式,只需要…...
SQL优化与性能——数据库设计优化
数据库设计优化是提高数据库性能、确保数据一致性和支持业务增长的关键环节。无论是大型企业应用还是小型项目,合理的数据库设计都能够显著提升系统性能、减少冗余数据、优化查询响应时间,并降低维护成本。本章将深入探讨数据库设计中的几个关键技术要点…...
FPGA存在的意义:为什么adc连续采样需要fpga来做,而不会直接用iic来实现
FPGA存在的意义:为什么adc连续采样需要fpga来做,而不会直接用iic来实现 原因ADS111x连续采样实现连续采样功能说明iic读取adc的数据速率 VS adc连续采样的速率adc连续采样的速率iic读取adc的数据速率结论分析 FPGA读取adc数据问题一:读取adc数…...
我们来学mysql -- 事务之概念(原理篇)
事务的概念 题记一个例子一致性隔离性原子性持久性 题记 在漫长的编程岁月中,存在一如既往地贯穿着工作,面试的概念这类知识点,事不关己当然高高挂起,精准踩坑时那心情也的却是日了🐶请原谅我的粗俗,遇到B…...
基于特征子空间的高维异常检测:一种高效且可解释的方法
本文将重点探讨一种替代传统单一检测器的方法:不是采用单一检测器分析数据集的所有特征,而是构建多个专注于特征子集(即子空间)的检测器系统。 在表格数据的异常检测实践中,我们的目标是识别数据中最为异常的记录,这种异常性可以…...
看不见的彼方:交换空间——小菜一碟
有个蓝色的链接,先去看看两年前的题目的write up (https://github.com/USTC-Hackergame/hackergame2022-writeups/blob/master/official/%E7%9C%8B%E4%B8%8D%E8%A7%81%E7%9A%84%E5%BD%BC%E6%96%B9/README.md) 从别人的write up中了解到&…...
YOLO模型训练后的best.pt和last.pt区别
在选择YOLO模型训练后的权重文件best.pt和last.pt时,主要取决于具体的应用场景:12 best.pt:这个文件保存的是在训练过程中表现最好的模型权重。通常用于推理和部署阶段,因为它包含了在验证集上表现最好的模型权重&#x…...
Pareidoscope - 语言结构关联工具
文章目录 关于 Pareidoscope安装使用方法输入格式语料库查询 将语料库转换为 SQLite3 数据库两种语言结构之间的关联简单词素分析关联共现和伴随词素分析相关的更大结构可视化关联结构 关于 Pareidoscope Pareidoscope 是一组 用于确定任意语言结构之间 关联的工具,…...
GPT(Generative Pre-trained Transformer) 和 Transformer的比较
GPT(Generative Pre-trained Transformer) 和 Transformer 的比较 flyfish 1. Transformer 是一种模型架构 Transformer 是一种通用的神经网络架构,由 Vaswani 等人在论文 “Attention Is All You Need”(2017)中提…...
软件无线电(SDR)的架构及相关术语
今天简要介绍实现无线电系统调制和解调的主要方法,这在软件定义无线电(SDR)的背景下很重要。 外差和超外差 无线电发射机有两种主要架构——一种是从基带频率直接调制到射频频率(称为外差),而第二种超外差是通过两个调制阶段来实…...
Python将Excel文件转换为JSON文件
工作过程中,需要从 Excel 文件中读取数据,然后交给 Python 程序处理数据,中间需要把 Excel 文件读取出来转为 json 格式,再进行下一步数据处理。 这里我们使用pandas库,这是一个强大的数据分析工具,能够方便地读取和处理各种数据格式。需要注意的是还需要引入openpyxl库,…...
排序算法之选择排序篇
思想: 每次从未排序的部分找出最小的元素,将其放到已排序部分的末尾 从数据结构中找到最小值,放到第一位,放到最前面,之后再从剩下的元素中找出第二小的值放到第二位,以此类推。 实现思路: 遍…...
sizeof和strlen区分,(好多例子)
sizeof算字节大小 带\0 strlen算字符串长度 \0之前...
A050-基于spring boot物流管理系统设计与实现
🙊作者简介:在校研究生,拥有计算机专业的研究生开发团队,分享技术代码帮助学生学习,独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取,记得注明来意哦~🌹 赠送计算机毕业设计600…...
[自然语言处理] NLP-RNN及其变体-干货
一、认识RNN模型 1 什么是RNN模型 RNN(Recurrent Neural Network), 中文称作循环神经网络, 它一般以序列数据为输入, 通过网络内部的结构设计有效捕捉序列之间的关系特征, 一般也是以序列形式进行输出. 一般单层神经网络结构: RNN单层网络结构: 以时间步对RNN进行展开后的单层…...
Elasticsearch ILM 索引生命周期管理讲解与实战
ES ILM 索引生命周期管理讲解与实战 Elasticsearch ILM索引生命周期管理:深度解析与实战演练1. 引言1.1 背景介绍1.2 研究意义2. ILM核心概念2.1 ILM的四个阶段2.1.1 Hot阶段2.1.2 Warm阶段2.1.3 Cold阶段2.1.4 Delete阶段3. ILM实战指南3.1 定义ILM策略3.1.1 创建ILM策略3.1.…...
Vue中实现动态标签页的切换优化与状态管理
1. 动态标签页的核心需求与实现思路 在后台管理系统这类多页面应用中,动态标签页几乎是标配功能。想象一下你正在使用某电商后台,同时开着商品管理、订单处理和用户分析三个页面,这时候标签页的流畅切换和状态保持就显得尤为重要。 我经历过一…...
OpenClaw+Qwen3-32B双剑合璧:个人知识库的智能维护方案
OpenClawQwen3-32B双剑合璧:个人知识库的智能维护方案 1. 为什么需要自动化知识管理 作为一个长期依赖个人知识库的内容创作者,我发现自己正陷入"信息过载"的困境。每天需要处理的网页文章、PDF报告、会议录音等碎片化内容超过20份ÿ…...
ArcSWAT实战避坑指南 | 从数据库配置到模型运行,详解常见报错与高效解决方案
1. ArcSWAT入门避坑:从安装到首次运行的关键准备 第一次接触ArcSWAT的水文研究者,往往会在安装环节就踩坑。我见过太多人因为版本兼容性问题,导致后续模型根本无法启动。这里分享几个血泪教训: ArcGIS版本选择是首要关键。虽然官方…...
JVM堆内存泄漏排查:从-Xmx设置到hprof文件分析的完整避坑指南
JVM堆内存泄漏排查:从参数配置到实战分析的完整方法论 最近在排查一个线上服务的内存泄漏问题时,我发现很多开发者对JVM内存问题的处理还停留在"遇到OOM就重启服务"的初级阶段。实际上,一套系统化的内存排查方法论不仅能快速定位问…...
OpenClaw技能开发:为QwQ-32B添加股票数据查询功能
OpenClaw技能开发:为QwQ-32B添加股票数据查询功能 1. 为什么需要开发股票查询技能 去年我在研究量化交易策略时,经常需要手动查询股票数据。每次打开浏览器、登录交易平台、输入代码、导出CSV的重复操作让我疲惫不堪。直到发现OpenClaw可以通过技能扩展…...
为什么你的MoveIt2 Python API总报错?ROS2环境变量与PYTHONPATH的隐藏陷阱
为什么你的MoveIt2 Python API总报错?ROS2环境变量与PYTHONPATH的隐藏陷阱 当你第一次在ROS2中尝试使用MoveIt2的Python API时,那种"ModuleNotFoundError: No module named moveit"的报错信息可能会让你抓狂。这不是因为你做错了什么ÿ…...
5大突破:抖音音乐批量下载与智能管理解决方案
5大突破:抖音音乐批量下载与智能管理解决方案 【免费下载链接】douyin-downloader 项目地址: https://gitcode.com/GitHub_Trending/do/douyin-downloader 在数字内容创作与音乐收藏领域,高效获取和管理抖音平台的音频资源一直是用户面临的核心挑…...
从零部署JetLinks社区版:一站式物联网平台本地化搭建实战
1. JetLinks社区版:物联网开发的瑞士军刀 第一次接触JetLinks社区版是在三年前的一个智能家居项目上。当时客户要求两周内搭建一个能管理5000设备的物联网平台,还要支持自定义协议开发。在对比了多个开源方案后,JetLinks的模块化设计让我眼前…...
Claude Code 速查表
其中的:键盘快捷键常规控制Ctrl C:取消输入 / 生成Ctrl D:退出会话Ctrl L:清屏Ctrl O:切换详细输出Ctrl R:反向搜索历史Ctrl G:在编辑器中打开提示Ctrl B:后台运行任务Ctrl …...
无限级数求和与Java实现优化教程
本教程详细讨论了如何准确计算形状 S -(2x)^2/2! (2x)^4/4! - (2x)^6/6! ... 指定范围内的无限级数 [0.1, 1.5] 内部和。文章首先分析了这个级数和 cos(2x) - 1 数学等价性,然后对Java代码中常见的错误进行了深入分析ÿ…...
