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

归并排序-逆序对

之前的文章里有写归并排序的最小和问题(归并排序-最小和-CSDN博客),逆序对问题其实跟最小和问题的本质一样:

逆序对:给定一个数据,从左往右,从第一个数开始,它右边每一个比它小的都能和它组成一个逆序对,比如{3, 4, 1, 2},对于3来说右边比它小的只有1,2,对于4来说,比它小的也只有1,2,对于1和2来说右边没有比它们自己小的,所以最终的逆序对是4,而{3, 4, 2,1}的逆序对则是5,因为2的右边有一个1比它小

最小和的解法过程中是寻找每一个数右边数组中比左边数组中大的数据有几个,而逆序对则寻找每一个数右边数组中比左边数组中小的数据有几个,只是在比较和拷贝的时候要从数组的最后一位开始,而不是下标为0的位置开始,由于思想同最小和是差不多的,这里就不细讲了,直接看代码:

public static void main(String[] args) {int arr[] = new int[]{3, 4, 1, 2};int length = arr.length;System.err.println(process(arr, 0, length - 1));for (int i = 0; i < length; i++) {System.err.println(arr[i]);}}private static int process(int arr[], int start, int end) {if (start == end) {return 0;}int middle = start + ((end - start) >> 1);//0 1return process(arr, start, middle) +process(arr, middle + 1, end) +merge(arr, start, middle, end);}/*** 核心逻辑就是对于右边数组中要严格比左边数组的数据小,满足条件就拷贝左边的数据* @param arr* @param start* @param middle* @param end* @return*/private static int merge(int arr[], int start, int middle, int end) {int result = 0;int[] help = new int[end - start + 1];int i = help.length - 1;int index1 = middle;int index2 = end;while (index1 >= start && index2 >= middle + 1) {result = result + (arr[index2] < arr[index1] ? (index2 - middle) : 0);help[i--] = arr[index2] < arr[index1] ? arr[index1--] : arr[index2--];}while (index1 >= start) {help[i--] = arr[index1--];}while (index2 >= middle + 1) {help[i--] = arr[index2--];}int length = help.length;for (int i1 = 0; i1 < length; i1++) {arr[start + i1] = help[i1];}return result;}

相关文章:

归并排序-逆序对

之前的文章里有写归并排序的最小和问题&#xff08;归并排序-最小和-CSDN博客&#xff09;&#xff0c;逆序对问题其实跟最小和问题的本质一样&#xff1a; 逆序对&#xff1a;给定一个数据&#xff0c;从左往右&#xff0c;从第一个数开始&#xff0c;它右边每一个比它小的都…...

爬虫笔记(二):实战58二手房

第一&#xff1a;给大家推荐一个爬虫的网课哈&#xff0c;码起来 第二&#xff1a;今夜主题&#xff1a;通过xpath爬取58二手房的title信息&#xff0c;也就是标红的位置~ 第三&#xff1a;先分析一波title所在的位置 打开按下f12打开抓包工具&#xff0c;即可看到网站的源码…...

一站式VR全景婚礼的优势表现在哪里?

你是否想过&#xff0c;婚礼也可以用一种全新的方式呈现&#xff0c;VR全景婚礼让每位用户沉浸式体验婚礼现场感。现在很多年轻人&#xff0c;都想让自己的婚礼与众不同&#xff0c;而VR全景婚礼也是未来发展的方向之一。 很多婚庆公司开通了VR婚礼这一服务&#xff0c;就是通过…...

【硅谷甄选】强制使用 pnpm 包管理器工具

强制使用pnpm包管理器工具 团队开发项目的时候&#xff0c;需要统一包管理器工具&#xff0c;因为不同包管理器工具下载同一个依赖&#xff0c;可能版本不一样&#xff0c;导致项目出现bug问题&#xff0c;因此包管理器工具需要统一管理。 在根目录创建scripts/preinstall.js…...

PHP AES加解密系列

PHP AES加密 使用PHP内置的mcrypt扩展库可以轻松地实现AES加密。 <?php function aes_encrypt($data, $key, $iv) {$cipher mcrypt_module_open(MCRYPT_RIJNDAEL_128, , MCRYPT_MODE_CBC, );mcrypt_generic_init($cipher, $key, $iv);$encrypted mcrypt_generic($ciphe…...

QT基础篇(13)QT5数据库

1.数据库基本概念 数据库&#xff08;Database&#xff09;是指存储、管理和组织数据的集合。它是一个组织化的、可持久化的数据集合&#xff0c;用于支持数据的存储、检索、更新和管理。 数据库系统&#xff08;Database System&#xff09;是建立在计算机上的数据管理系统&…...

ctfshow信息收集(web1-web20)

目录 web1 web2 web3 web4 web5 web6 web7 web9 web10 web11 web14 web15 web16 web17 web18 web19 web20 web1 根据提示的孩子开发的时候注释没有被及时删除 web2 js原因无法查看源代码 第一种方法 在url前加入 view-source&#xff1a; 会显示页面源代…...

从零学习Hession RPC

为什么学习Hessian RPC&#xff1f; 存粹的RPC&#xff0c;只解决PRC的四个核心问题&#xff08;1.网络通信2.协议 3.序列化 4.代理&#xff09;Java写的HessianRPC落伍了&#xff0c;但是它的序列化方式还保存着&#xff0c;被Dubbo(Hessian Lite)使用。 被落伍&#xff0c;只…...

实施精细化管理的六大关键步骤

在当今高度竞争的市场环境中&#xff0c;企业若想脱颖而出&#xff0c;必须实现精细化管理。这不仅是为了提高效率&#xff0c;更是为了确保在复杂多变的市场中保持领先地位。通过以下六个关键步骤&#xff0c;企业可以构建一个强大的精细化管理体系&#xff0c;从而为未来的成…...

QT+C++环境调用python函数可以进入python环境和模块,但是调用功能函数错误

QTC环境使用Python.h调用python函数可以进入python环境和模块&#xff0c;但是调用功能函数错误 背景&#xff1a; 定义的python函数使用了其他库封装好的函数&#xff0c;在python环境下运行此程序毫无问题但是QT调用却显示调用此函数出错&#xff0c;此时调用此.py文件内的其…...

2024.1.24力扣每日一题——美丽塔I

2024.1.24 题目来源我的题解方法一 暴力枚举方法二 单调栈前、后缀和 题目来源 力扣每日一题&#xff1b;题序&#xff1a;2865 我的题解 方法一 暴力枚举 将每个位置都作为山峰来进行遍历&#xff0c;计算每个山峰下的最大山脉数组和 时间复杂度&#xff1a;O( n 2 n^2 n2)…...

视频监控平台EasyCVR增加fMP4流媒体视频格式及其应用场景介绍

近期我们在视频监控管理平台EasyCVR系统中新增了HTTP-FMP4播放协议&#xff0c;今天我们就来聊聊该协议的特点和应用。 fMP4&#xff08;Fragmented MPEG-4&#xff09;是基于MPEG-4 Part 12的流媒体格式&#xff0c;是流媒体的一项重要技术&#xff0c;因为它能通过互联网传送…...

使用Python的pygame库实现迷宫游戏

使用Python的pygame库实现迷宫游戏 关于Python中pygame游戏模块的安装使用可见 https://blog.csdn.net/cnds123/article/details/119514520 先给出效果图&#xff1a; 这个游戏每次运行能自动随机生成迷宫布局。 在这个游戏中&#xff0c;玩家将使用键盘箭头键来移动&#x…...

Linux新手村必备!这些常用操作命令你掌握了吗?

在计算机的世界里&#xff0c;Linux操作系统以其强大的功能和灵活性受到了广大程序员和IT爱好者的喜爱。然而&#xff0c;对于初学者来说&#xff0c;Linux的操作命令可能会显得有些复杂和难以理解。 今天&#xff0c;我们就来一起探索一些Linux常用操作命令&#xff0c;让你的…...

ReactNative进阶(三十六):iPad横屏适配

文章目录 一、前言二、实现思路三、延伸阅读四、拓展阅读 一、前言 应用RN技术栈实现APP上线后&#xff0c;业务部门领导会上反馈未实现ipad横屏全屏展示&#xff0c;用户体验较差。由此&#xff0c;一场pad横屏全屏展示的APP调优工作由此开展。 二、实现思路 时间紧任务重&…...

jsx中使用插槽

1. jsx语法中使用插槽 以elementplus ElPopconfirm 为例 <el-popconfirm title"Are you sure to delete this?"><template #reference><el-button>Delete</el-button></template></el-popconfirm>使用 slots: {default: (dat…...

CentOS服务器拒绝SSH登录

当CentOS服务器拒绝SSH登录时&#xff0c;有几个可能的原因和解决方法&#xff1a; 检查网络连接&#xff1a;确保服务器与您的计算机之间的网络连接是正常的。您可以尝试使用其他网络连接或ping服务器以检查是否能够访问。 确认SSH服务正在运行&#xff1a;在服务器上确认SSH…...

React16源码: React中的completeUnitOfWork的源码实现

completeUnitOfWork 1 &#xff09;概述 各种不同类型组件的一个更新过程对应的是在执行 performUnitOfWork 里面的 beginWork 阶段它是去向下遍历一棵 fiber 树的一侧的子节点&#xff0c;然后遍历到叶子节点为止&#xff0c;以及 return 自己 child 的这种方式在 performUni…...

uniapp移动端——企业微信H5调用jssdk实现扫一扫,通过weixin-java-cp获取ticket签名,配置config

背景&#xff1a; 使用企业微信开发扫一扫功能 可信域名验证 (1)企业微信的可信域名需要和企业微信的备案主体一致。 域名备案主体可通过站长工具查看域名备案主体。https://icp.chinaz.com/ 企业微信备案主体可以咨询管理员 &#xff08;2&#xff09;通过nginx配置域名归…...

【前端基础--1】

为后面爬虫打基础 使用Visual Studio Code&#xff08;VS Code&#xff09; https://code.visualstudio.com/#alt-downloads 网页基础 创建一个html网页 新建一个文件 文件名后缀.html 书写网页模板 html:5 回车键&#xff08;或者Tab键&#xff09;英文感叹号! 回…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...

从实验室到产业:IndexTTS 在六大核心场景的落地实践

一、内容创作&#xff1a;重构数字内容生产范式 在短视频创作领域&#xff0c;IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色&#xff0c;生成的 “各位吴彦祖们大家好” 语音相似度达 97%&#xff0c;单条视频播放量突破百万…...

第22节 Node.js JXcore 打包

Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本&#xff0c;基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...