[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. 计算右侧小于当前元素的个数
题目描述: 给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。 题目链接: . - 力扣(LeetCode) 题目主要思路&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机制需要以下几个步骤: 1. 规定格式 当添加新的模块(如Attention机制模块)时,需要像定义[convolutional]、[maxpool]等层在cfg文件中的格式一样,对新模块进行格式规定。例如对于SE模块&a…...
单点登录Apereo CAS 7.1安装配置教程
笔者目前正在做一个单点登录的课题,历时较长总算摸到一些门路,其中的辛酸不易按下不表。截至本文发布,CAS的最新版本为7.1。由于涉及到课题内容,而且内容比较新,整理试验不容易,暂时只对VIP开放,后续课题完成后会完全开放,敬请谅解。 CAS项目区别 在CAS的项目选择上,…...
windows C++-移除界面工作线程(一)
本文档演示了如何使用并发运行时将 Microsoft 基础类 (MFC) 应用程序中由用户界面 (UI) 线程执行的工作移动到工作线程。 本文档还演示了如何提高冗长绘制操作的性能。 通过将阻塞性操作(例如,绘制)卸载到工作线程来从 UI 线程中移除工作&am…...
Qt小bug — LINK : fatal error LNK1158: 无法运行“rc.exe“
Qt小bug —— LINK :fatal error LNK1158:无法运行"rc.exe" 环境 Qt 5.14.2 MSVC 2015 x64 现象 解决 在电脑上找到rc.exe 和rcdll.dll (一般在C:\Program Files(x86)\Windows Kits*\bin\x64下面)拷贝到 C:\Qt\Qt5…...
c++小游戏
目录 狼人杀 走迷宫 炸弹人 贪吃蛇 飞翔的小鸟 跑酷 吃豆人 飞机大战 人生模拟器 坦克大战 修仙模拟器 搜集了一些小游戏,名字下是个人是个人喜欢度,可供参考~ 狼人杀 ❤❤❤❤ #include<bits/stdc.h> #include<cstdio> #incl…...
k8s为什么用Calico
Calico是一种开源的网络和安全解决方案,主要用于容器、虚拟机、宿主机之间的网络连接。 它支持Kubernetes、OpenShift、Docker EE、OpenStack等PaaS或IaaS平台,提供高效的网络通信和安全控制功能12。 Calico的核心组件包括Felix、etcd、BIRD等。F…...
HashMap 和 Hashtable 有什么区别?
HashMap和Hashtable都是Java中常用的存储键值对的集合类,它们都实现了Map接口,但二者之间存在一些显著的区别。以下是对HashMap和Hashtable区别的详细归纳: 一、线程安全性 HashMap:是非线程安全的,即多个线程可以同…...
【机器学习】深度学习、强化学习和深度强化学习?
深度学习、强化学习和深度强化学习是机器学习的三个重要子领域。它们有着各自独特的应用场景和研究目标,虽然都属于机器学习的范畴,但各自的实现方式和侧重点有所不同。 1. 深度学习(Deep Learning) 深度学习是一种基于神经网络的…...
fastadmin 多商户模式下侧边栏跳转路径BUG
记录:仅作自己项目记录,在一个域名下部署多套项目时,若不是多商户模式项目会出现跳转路径问题。 修改 \manystore\library\Auth.php 文件的 getSidebar 方法 // 1 改为: $v[url] isset($v[url]) && $v[url] ? $v[url]…...
java内置的四种函数式接口
供给型:Supplier 无入参,有返回值。 FunctionalInterface public interface Supplier<T> {T get();}消费型:Consumer 有入参,无返回值。 FunctionalInterface public interface Consumer<T> {void accept(T t);de…...
如何获取 uni-app 应用发布所需的证书、私钥与配置文件
引言 在开发和发布iOS应用时,开发者常常会面临一系列复杂的证书、私钥密码以及配置文件的管理问题。这些配置不仅影响到应用的开发调试,还决定了应用是否能够顺利通过审核并发布到App Store。对于使用uni-app进行开发的开发者来说,自动生成的…...
TCP网络通信——多线程
前面分别用多进程和多路复用完成了TCP网络通信,本文就来讲讲多线程的TCP通信。首先来了解一下线程的概念: 1、线程是进程的执行路线,它是进程内部的控制序列,或者说线程是进程的一部分(进程是一个资源单位,线程是执行单…...
【exp报错注入】
整数范围 最大整数 exp 函数介绍 报错盲注注入 payload分析 709C-ASCII 值就等于我们下面的 7091-1 ,C就是我们要猜的值,当我们猜测的值和ASCII码相等时,那么exp就不会出现报错,因为1-1还是等于709: 练习 id1 an…...
基于SpringBoot问卷调查系统小程序【附源码】
基于SpringBoot问卷调查系统小程序 效果如下: 管理员登录界面 管理员功能界面 调查人管理界面 问卷调查管理界面 问卷题目管理界面 用户登录界面 APP首页界面 公告信息界面 研究背景 随着科学技术的飞速发展,各行各业都在努力与现代先进技术接轨&…...
LLM - 配置 GraphRAG + Ollama 服务 构建 中文知识图谱
欢迎关注我的CSDN:https://spike.blog.csdn.net/ 本文地址:https://spike.blog.csdn.net/article/details/142795151 免责声明:本文来源于个人知识与公开资料,仅用于学术交流,欢迎讨论,不支持转载。 GraphR…...
简单认识redis - 6 redis 存储速度快的原因
1基于内存存储 缓存(内存)读写速度很快,相比于磁盘存储的Mysql 省去了磁盘I/O的次数。 2.高效的数据结构 SDS动态字符串: 1.字符串长度处理:Redis获取字符串长度,时间复杂度为O(1),而C语言中&am…...
【Qt Quick】状态:State 使用
State 是 Qt Quick 中管理界面组件状态的关键工具。它允许我们定义组件的不同状态,并且在用户交互或事件发生时进行状态切换,从而实现属性、外观和行为的动态变化。通过使用 State,可以避免复杂的条件逻辑,使代码更加简洁和可维护…...
ICE/TURN/STUN/Coturn服务器搭建
ICE 当我们想要实现在公网环境下的语音/视频通话功能时,就需要用到ICE交互式连接建立。ICE不是一种协议,整合了 STUN 和 TURN 两种协议(用于 NAT 穿透)的框架。 ICE的主要目标是解决NAT(网络地址转换)穿越…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
