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

[LeetCode] 315. 计算右侧小于当前元素的个数

题目描述:

给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

题目链接:

. - 力扣(LeetCode)

题目主要思路:

其实跟 “LCR170. 交易逆序对的总数” 那道题差不多,就是多了个数组来记录原始的index,因为counts[i]的值是nums[i]右侧小于nums[i]的元素的数量,建议先理解 “LCR170. 交易逆序对的总数” 这道题的解题思路后再挑战该题。

LCR170. 交易逆序对的总数题目思路及链接:[LeetCode] LCR170. 交易逆序对的总数-CSDN博客

解题代码:

class Solution {
public:vector<int> counts; // 返回的数组vector<int> index;  // 记录原始下标的数组int tmpNums[500010];int tmpIndex[500010];vector<int> countSmaller(vector<int>& nums) {counts.resize(nums.size());index.resize(nums.size());for (int i = 0; i < nums.size()-1; ++i) {index[i] = i;}mergeSort(nums, 0, nums.size()-1);return counts;}void mergeSort(vector<int>& nums, int left, int right){if (left >= right) return;int mid = (left + right) >> 1;mergeSort(nums, left, mid);mergeSort(nums, mid+1, right);int cur1 = left, cur2 = mid+1, i = 0;while (cur1 <= mid && cur2 <= right) {// 排降序if (nums[cur1] <= nums[cur2]) {tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];  // 记录更换位置后nums[i]原本的index}else{counts[index[cur1]] += right-cur2+1;tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];  // 记录更换位置后nums[i]原本的index}}while (cur1 <= mid) {tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];  // 记录更换位置后nums[i]原本的index}while (cur2 <= right) {tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];  // 记录更换位置后nums[i]原本的index}for (int i = left; i <= right; ++i) {nums[i] = tmpNums[i-left];index[i] = tmpIndex[i-left];  // 将记录更换位置后的原始index写入到index数组中}}
};

相关文章:

[LeetCode] 315. 计算右侧小于当前元素的个数

题目描述&#xff1a; 给你一个整数数组 nums &#xff0c;按要求返回一个新数组 counts 。数组 counts 有该性质&#xff1a; counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。 题目链接&#xff1a; . - 力扣&#xff08;LeetCode&#xff09; 题目主要思路&a…...

【hot100-java】二叉树展开为链表

二叉树篇。 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* …...

如何在在 YOLOv3模型中添加Attention机制

在YOLOv3模型中添加Attention机制需要以下几个步骤&#xff1a; 1. 规定格式 当添加新的模块&#xff08;如Attention机制模块&#xff09;时&#xff0c;需要像定义[convolutional]、[maxpool]等层在cfg文件中的格式一样&#xff0c;对新模块进行格式规定。例如对于SE模块&a…...

单点登录Apereo CAS 7.1安装配置教程

笔者目前正在做一个单点登录的课题,历时较长总算摸到一些门路,其中的辛酸不易按下不表。截至本文发布,CAS的最新版本为7.1。由于涉及到课题内容,而且内容比较新,整理试验不容易,暂时只对VIP开放,后续课题完成后会完全开放,敬请谅解。 CAS项目区别 在CAS的项目选择上,…...

windows C++-移除界面工作线程(一)

本文档演示了如何使用并发运行时将 Microsoft 基础类 (MFC) 应用程序中由用户界面 (UI) 线程执行的工作移动到工作线程。 本文档还演示了如何提高冗长绘制操作的性能。 通过将阻塞性操作&#xff08;例如&#xff0c;绘制&#xff09;卸载到工作线程来从 UI 线程中移除工作&am…...

Qt小bug — LINK : fatal error LNK1158: 无法运行“rc.exe“

Qt小bug —— LINK &#xff1a;fatal error LNK1158&#xff1a;无法运行"rc.exe" 环境 Qt 5.14.2 MSVC 2015 x64 现象 解决 在电脑上找到rc.exe 和rcdll.dll &#xff08;一般在C:\Program Files(x86)\Windows Kits*\bin\x64下面&#xff09;拷贝到 C:\Qt\Qt5…...

c++小游戏

目录 狼人杀 走迷宫 炸弹人 贪吃蛇 飞翔的小鸟 跑酷 吃豆人 飞机大战 人生模拟器 坦克大战 修仙模拟器 搜集了一些小游戏&#xff0c;名字下是个人是个人喜欢度&#xff0c;可供参考~ 狼人杀 ❤❤❤❤ #include<bits/stdc.h> #include<cstdio> #incl…...

k8s为什么用Calico

‌Calico是一种开源的网络和安全解决方案&#xff0c;主要用于容器、虚拟机、宿主机之间的网络连接。‌ 它支持Kubernetes、OpenShift、Docker EE、OpenStack等PaaS或IaaS平台&#xff0c;提供高效的网络通信和安全控制功能‌12。 Calico的核心组件包括Felix、etcd、BIRD等。F…...

HashMap 和 Hashtable 有什么区别?

HashMap和Hashtable都是Java中常用的存储键值对的集合类&#xff0c;它们都实现了Map接口&#xff0c;但二者之间存在一些显著的区别。以下是对HashMap和Hashtable区别的详细归纳&#xff1a; 一、线程安全性 HashMap&#xff1a;是非线程安全的&#xff0c;即多个线程可以同…...

【机器学习】深度学习、强化学习和深度强化学习?

深度学习、强化学习和深度强化学习是机器学习的三个重要子领域。它们有着各自独特的应用场景和研究目标&#xff0c;虽然都属于机器学习的范畴&#xff0c;但各自的实现方式和侧重点有所不同。 1. 深度学习&#xff08;Deep Learning&#xff09; 深度学习是一种基于神经网络的…...

fastadmin 多商户模式下侧边栏跳转路径BUG

记录&#xff1a;仅作自己项目记录&#xff0c;在一个域名下部署多套项目时&#xff0c;若不是多商户模式项目会出现跳转路径问题。 修改 \manystore\library\Auth.php 文件的 getSidebar 方法 // 1 改为&#xff1a; $v[url] isset($v[url]) && $v[url] ? $v[url]…...

java内置的四种函数式接口

供给型&#xff1a;Supplier 无入参&#xff0c;有返回值。 FunctionalInterface public interface Supplier<T> {T get();}消费型&#xff1a;Consumer 有入参&#xff0c;无返回值。 FunctionalInterface public interface Consumer<T> {void accept(T t);de…...

如何获取 uni-app 应用发布所需的证书、私钥与配置文件

引言 在开发和发布iOS应用时&#xff0c;开发者常常会面临一系列复杂的证书、私钥密码以及配置文件的管理问题。这些配置不仅影响到应用的开发调试&#xff0c;还决定了应用是否能够顺利通过审核并发布到App Store。对于使用uni-app进行开发的开发者来说&#xff0c;自动生成的…...

TCP网络通信——多线程

前面分别用多进程和多路复用完成了TCP网络通信&#xff0c;本文就来讲讲多线程的TCP通信。首先来了解一下线程的概念&#xff1a; 1、线程是进程的执行路线&#xff0c;它是进程内部的控制序列&#xff0c;或者说线程是进程的一部分(进程是一个资源单位&#xff0c;线程是执行单…...

【exp报错注入】

整数范围 最大整数 exp 函数介绍 报错盲注注入 payload分析 709C-ASCII 值就等于我们下面的 7091-1 &#xff0c;C就是我们要猜的值&#xff0c;当我们猜测的值和ASCII码相等时&#xff0c;那么exp就不会出现报错&#xff0c;因为1-1还是等于709&#xff1a; 练习 id1 an…...

基于SpringBoot问卷调查系统小程序【附源码】

基于SpringBoot问卷调查系统小程序 效果如下&#xff1a; 管理员登录界面 管理员功能界面 调查人管理界面 问卷调查管理界面 问卷题目管理界面 用户登录界面 APP首页界面 公告信息界面 研究背景 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&…...

LLM - 配置 GraphRAG + Ollama 服务 构建 中文知识图谱

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/142795151 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 GraphR…...

简单认识redis - 6 redis 存储速度快的原因

1基于内存存储 缓存&#xff08;内存&#xff09;读写速度很快&#xff0c;相比于磁盘存储的Mysql 省去了磁盘I/O的次数。 2.高效的数据结构 SDS动态字符串&#xff1a; 1.字符串长度处理&#xff1a;Redis获取字符串长度&#xff0c;时间复杂度为O(1)&#xff0c;而C语言中&am…...

【Qt Quick】状态:State 使用

State 是 Qt Quick 中管理界面组件状态的关键工具。它允许我们定义组件的不同状态&#xff0c;并且在用户交互或事件发生时进行状态切换&#xff0c;从而实现属性、外观和行为的动态变化。通过使用 State&#xff0c;可以避免复杂的条件逻辑&#xff0c;使代码更加简洁和可维护…...

ICE/TURN/STUN/Coturn服务器搭建

ICE 当我们想要实现在公网环境下的语音/视频通话功能时&#xff0c;就需要用到ICE交互式连接建立。ICE不是一种协议&#xff0c;整合了 STUN 和 TURN 两种协议&#xff08;用于 NAT 穿透&#xff09;的框架。 ICE的主要目标是解决NAT&#xff08;网络地址转换&#xff09;穿越…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...