当前位置: 首页 > 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;英文感叹号! 回…...

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

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

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...