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

【算法题】翻转对

题目:

给定一个数组 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;}}
}

相关文章:

【算法题】翻转对

题目&#xff1a; 给定一个数组 nums &#xff0c;如果 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图片照片&#xff0c;但不知何故&#xff0c;您意识到一些重要的 JPEG /PNG图片文件丢失或被删除&#xff0c;它们对您来说意义重大&#xff0c;您想要找回它们. 4 种最佳 JPEG/PNG图片 恢复软件 要成功执行 JPEG /PNG图片…...

位置信息API

位置信息API 一、获取当前位置&#xff1a;wx.getLocation(object)二、选择位置&#xff1a;wx.chooseLocation(object)三、打开位置&#xff1a;wx.openLocation(object)四、监听位置事件五、地图组件控制API六、收货地址API&#xff1a;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 速度快的原因除了它是内存数据库&#xff0c;使得所有的操作都在内存上进行之外&#xff0c;还有一个重要因素&#xff0c;它实现的数据结构&#xff0c;使得我们对数据进行增删查改操作时&#xff0c;Redis 能高效的处理。 因此&#xff0c;这次我…...

一文详解多模态大模型发展及高频因子计算加速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 可以略过&#xff0c;改为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的动态增删显示实现方式

目的 端应用程序或者编辑器基本都支持工具栏快捷功能的动态增删&#xff0c;即通过在菜单栏上打钩就可以在工具栏上看到相应功能的快捷按钮&#xff0c;取消打钩则在工具栏上就移除了该功能的快捷按钮。那么Qt如何实现这个功能&#xff0c;本篇目的就是记录实现此功能的方法及思…...

十四天学会C++之第八天:文件操作

1. 文件的打开和关闭 文件操作的基本概念。打开文件&#xff1a;使用fstream库打开文件以供读写。关闭文件&#xff1a;确保文件在使用完毕后正确关闭。 文件的打开和关闭&#xff1a;C 文件操作入门 在C编程中&#xff0c;文件操作是一项重要的任务&#xff0c;可以读取和写…...

基于(N-1)×(N-1)棋盘的解的情况推出N×N棋盘的解的情况的N皇后问题

N皇后问题是一个比较经典的问题&#xff0c;其主要目标是在NN的棋盘上&#xff0c;放置N个皇后&#xff0c;要求所有皇后之间不能互相攻击&#xff0c;即任意两个皇后不能处在同一行、同一列或同一对角线上。解决该问题可以采用递归的方式&#xff0c;基于(N-1)棋盘的解的情况推…...

Vue mixin混入

可以把多个组件中共有的配置提取出来构成一个混入。 一、配置混入 &#xff08;一&#xff09; 创建mixin.js 这里的名字可以自定义&#xff0c;但是为了方便识别&#xff0c;多数场景下都写mixin。 mixin.js 要创建在src目录下&#xff0c;与main.js平级&#xff1a; &…...

基于 FFmpeg 的跨平台视频播放器简明教程(十):在 Android 运行 FFmpeg

系列文章目录 基于 FFmpeg 的跨平台视频播放器简明教程&#xff08;一&#xff09;&#xff1a;FFMPEG Conan 环境集成基于 FFmpeg 的跨平台视频播放器简明教程&#xff08;二&#xff09;&#xff1a;基础知识和解封装&#xff08;demux&#xff09;基于 FFmpeg 的跨平台视频…...

正点原子嵌入式linux驱动开发——Linux LCD驱动

LCD是很常用的一个外设&#xff0c;通过LCD可以显示绚丽的图片、界面等&#xff0c;提交人机交互的效率。STM32MP1提供了一个LTDC接口用于连接RGB接口的液晶屏。本章就来学校一下如何在Linux下驱动LCD屏。 LCD和LTDC简介 LCD简介 这里在当时学习stm32裸机开发的时候就学过了…...

2-Java进阶知识总结-6-多线程

文章目录 多线程--基本概念并发和并行进程和线程多线程 多线程--实现方式一&#xff0c;继承Thread类方法介绍实现步骤注意事项 方式二&#xff0c;实现Runnable接口Thread构造方法实现步骤 方式三&#xff0c;实现Callable接口方法介绍实现步骤 三种多线程实现方法对比 多线程…...

openwrt下游设备在校园网(DLUT-LingShui)中使用ipv6网络

背景&#xff1a;校园网最多支持6台设备的无感认证&#xff0c;需要使用路由器(本人使用openwrt系统)为更多的设备提供网络&#xff0c;但校园网分配的ipv6地址子网为/128&#xff0c;不能为路由器下的设备分配全球ipv6地址&#xff0c;因此需要使用nat6转发下游设备的局域网ip…...

10个基于.Net开发的Windows开源软件项目

1、基于.NET的强大软件开发工具 一个基于.Net Core构建的简单、跨平台快速开发框架。JNPF开发平台前后端封装了上千个常用类&#xff0c;方便扩展&#xff1b;集成了代码生成器&#xff0c;支持前后端业务代码生成&#xff0c;满足快速开发&#xff0c;提升工作效率&#xff1b…...

Java多线程秘籍,掌握这5种方法,让你的代码优化升级

介绍5种多线程方法&#xff0c;助您提高编码效率&#xff01; 如果您的应用程序与那些能够同时处理多个任务的应用程序相比表现不佳&#xff0c;很可能是因为它是单线程的。解决这个问题的方法之一是采用多线程技术。 以下是一些可以考虑的方法&#xff1a; 线程&#xff08;…...

npm install报错 缺少python

报错信息&#xff1a; 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日志记录&#xff0c;可协助排查定位数据库问题。生产开启会有一定的性能消耗&#xff0c;建议打开 SQL 日志异步刷盘功能 1.配置sqllog.ini文件 sqllog.ini 用于 SQL 日志的配置&#xff0c;当且仅当 INI 参数 SVR_LOG1 时使用。 运行中的数据库实例&#xff0c;可…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...