【算法题】翻转对
题目:
给定一个数组 nums ,如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
示例 1:
输入: [1,3,2,3,1]
输出: 2
示例 2:
输入: [2,4,3,5,1]
输出: 3
注意:
给定数组的长度不会超过50000。
输入数组中的所有数字都在32位整数的表示范围内。
java代码:
class Solution {public int reversePairs(int[] nums) {if (nums.length == 0) {return 0;}return reversePairsRecursive(nums, 0, nums.length - 1);}public int reversePairsRecursive(int[] nums, int left, int right) {if (left == right) {return 0;} else {int mid = (left + right) / 2;int n1 = reversePairsRecursive(nums, left, mid);int n2 = reversePairsRecursive(nums, mid + 1, right);int ret = n1 + n2;// 首先统计下标对的数量int i = left;int j = mid + 1;while (i <= mid) {while (j <= right && (long) nums[i] > 2 * (long) nums[j]) {j++;}ret += j - mid - 1;i++;}// 随后合并两个排序数组int[] sorted = new int[right - left + 1];int p1 = left, p2 = mid + 1;int p = 0;while (p1 <= mid || p2 <= right) {if (p1 > mid) {sorted[p++] = nums[p2++];} else if (p2 > right) {sorted[p++] = nums[p1++];} else {if (nums[p1] < nums[p2]) {sorted[p++] = nums[p1++];} else {sorted[p++] = nums[p2++];}}}for (int k = 0; k < sorted.length; k++) {nums[left + k] = sorted[k];}return ret;}}
}相关文章:
【算法题】翻转对
题目: 给定一个数组 nums ,如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。 示例 1: 输入: [1,3,2,3,1] 输出: 2 示例 2: 输入: [2,4,3,5,1] 输出: 3 注意: 给定数组的长…...
适用于 Mac 或 Windows 的 4 种最佳 JPEG/PNG图片 恢复软件
您的计算机或外部存储驱动器上很可能有大量 JPEG /PNG图片照片,但不知何故,您意识到一些重要的 JPEG /PNG图片文件丢失或被删除,它们对您来说意义重大,您想要找回它们. 4 种最佳 JPEG/PNG图片 恢复软件 要成功执行 JPEG /PNG图片…...
位置信息API
位置信息API 一、获取当前位置:wx.getLocation(object)二、选择位置:wx.chooseLocation(object)三、打开位置:wx.openLocation(object)四、监听位置事件五、地图组件控制API六、收货地址API:wx.chooseAddress(object) 一、获取当前…...
MySQL——九、SQL编程
MySQL 一、触发器1、触发器简介2、创建触发器3、一些常见示例 二、存储过程1、什么是存储过程或者函数2、优点3、存储过程创建与调用 三、存储函数1、存储函数创建和调用2、修改存储函数3、删除存储函数 四、游标1、声明游标2、打开游标3、使用游标4、关闭游标游标案例 一、触发…...
threejs(4)-纹理材质高级操作
一、纹理重复_缩放_旋转_位移操作 // 导入threejs import * as THREE from "three"; // 导入轨道控制器 import { OrbitControls } from "three/examples/jsm/controls/OrbitControls.js"; // 导入lil.gui import { GUI } from "three/examples/jsm/l…...
Redis | 数据结构(01)
这里写自定义目录标题 Redis 速度快的原因除了它是内存数据库,使得所有的操作都在内存上进行之外,还有一个重要因素,它实现的数据结构,使得我们对数据进行增删查改操作时,Redis 能高效的处理。 因此,这次我…...
一文详解多模态大模型发展及高频因子计算加速GPU算力 | 英伟达显卡被限,华为如何力挽狂澜?
★深度学习、机器学习、多模态大模型、深度神经网络、高频因子计算、GPT-4、预训练语言模型、Transformer、ChatGPT、GenAI、L40S、A100、H100、A800、H800、华为、GPU、CPU、英伟达、NVIDIA、卷积神经网络、Stable Diffusion、Midjourney、Faster R-CNN、CNN 随着人工智能技术…...
debian 10 安装apache2 zabbix
nginx 可以略过,改为apache2 apt updateapt-get install nginx -ynginx -v nginx version: nginx/1.14.2mysql 安装参考linux debian10 安装mysql5.7_debian apt install mysql5.7-CSDN博客 Install and configure Zabbix for your platform a. Install Zabbix re…...
Qt之菜单栏、工具栏、状态栏介绍及工具栏QAction的动态增删显示实现方式
目的 端应用程序或者编辑器基本都支持工具栏快捷功能的动态增删,即通过在菜单栏上打钩就可以在工具栏上看到相应功能的快捷按钮,取消打钩则在工具栏上就移除了该功能的快捷按钮。那么Qt如何实现这个功能,本篇目的就是记录实现此功能的方法及思…...
十四天学会C++之第八天:文件操作
1. 文件的打开和关闭 文件操作的基本概念。打开文件:使用fstream库打开文件以供读写。关闭文件:确保文件在使用完毕后正确关闭。 文件的打开和关闭:C 文件操作入门 在C编程中,文件操作是一项重要的任务,可以读取和写…...
基于(N-1)×(N-1)棋盘的解的情况推出N×N棋盘的解的情况的N皇后问题
N皇后问题是一个比较经典的问题,其主要目标是在NN的棋盘上,放置N个皇后,要求所有皇后之间不能互相攻击,即任意两个皇后不能处在同一行、同一列或同一对角线上。解决该问题可以采用递归的方式,基于(N-1)棋盘的解的情况推…...
Vue mixin混入
可以把多个组件中共有的配置提取出来构成一个混入。 一、配置混入 (一) 创建mixin.js 这里的名字可以自定义,但是为了方便识别,多数场景下都写mixin。 mixin.js 要创建在src目录下,与main.js平级: &…...
基于 FFmpeg 的跨平台视频播放器简明教程(十):在 Android 运行 FFmpeg
系列文章目录 基于 FFmpeg 的跨平台视频播放器简明教程(一):FFMPEG Conan 环境集成基于 FFmpeg 的跨平台视频播放器简明教程(二):基础知识和解封装(demux)基于 FFmpeg 的跨平台视频…...
正点原子嵌入式linux驱动开发——Linux LCD驱动
LCD是很常用的一个外设,通过LCD可以显示绚丽的图片、界面等,提交人机交互的效率。STM32MP1提供了一个LTDC接口用于连接RGB接口的液晶屏。本章就来学校一下如何在Linux下驱动LCD屏。 LCD和LTDC简介 LCD简介 这里在当时学习stm32裸机开发的时候就学过了…...
2-Java进阶知识总结-6-多线程
文章目录 多线程--基本概念并发和并行进程和线程多线程 多线程--实现方式一,继承Thread类方法介绍实现步骤注意事项 方式二,实现Runnable接口Thread构造方法实现步骤 方式三,实现Callable接口方法介绍实现步骤 三种多线程实现方法对比 多线程…...
openwrt下游设备在校园网(DLUT-LingShui)中使用ipv6网络
背景:校园网最多支持6台设备的无感认证,需要使用路由器(本人使用openwrt系统)为更多的设备提供网络,但校园网分配的ipv6地址子网为/128,不能为路由器下的设备分配全球ipv6地址,因此需要使用nat6转发下游设备的局域网ip…...
10个基于.Net开发的Windows开源软件项目
1、基于.NET的强大软件开发工具 一个基于.Net Core构建的简单、跨平台快速开发框架。JNPF开发平台前后端封装了上千个常用类,方便扩展;集成了代码生成器,支持前后端业务代码生成,满足快速开发,提升工作效率;…...
Java多线程秘籍,掌握这5种方法,让你的代码优化升级
介绍5种多线程方法,助您提高编码效率! 如果您的应用程序与那些能够同时处理多个任务的应用程序相比表现不佳,很可能是因为它是单线程的。解决这个问题的方法之一是采用多线程技术。 以下是一些可以考虑的方法: 线程(…...
npm install报错 缺少python
报错信息: Building:E:tolsnvmnodesnodeexe : ode emos ant-desig-we-eos odemodules node-gypbintnode-gp.s rebld -verbose -Libsass_ext --Libsas_cflags- lags --libsass_librarygyp info it worked if it ends with ok gyp verb cli [ gyp verb cliE: toolsnv…...
达梦:开启sql日志记录
前言 开启sql日志记录,可协助排查定位数据库问题。生产开启会有一定的性能消耗,建议打开 SQL 日志异步刷盘功能 1.配置sqllog.ini文件 sqllog.ini 用于 SQL 日志的配置,当且仅当 INI 参数 SVR_LOG1 时使用。 运行中的数据库实例,可…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
