牛客热题:逆序对数量

📟作者主页:慢热的陕西人

🌴专栏链接:力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言

在这里插入图片描述

文章目录

  • 牛客热题:逆序对数量
    • 题目链接
    • 方法一:归并排序
      • 思路
      • 代码
      • 复杂度

牛客热题:逆序对数量

题目链接

数组中的逆序对_牛客题霸_牛客网 (nowcoder.com)

方法一:归并排序

思路

  • 逆序对:数组左边边的元素大于右边的元素则被称为一个逆序对

  • 首先归并排序的思路就是将两个原本有序的数组合并为一个数组

  • 归并排序内部又是将原数组分成很多个小区间,然后相邻的小区间再进行合并

  • 那么在合并的途中,就涉及到那些元素的位置需要交换。

  • 需要交换的位置就是一个逆序对,但是因为待合并的数组都是有序的,所以其之后的每一个元素也都会产生逆序对 即:a[i] > a[j],则a[i] 和它后面的元素都大于 a[j](其中i,j是两个待合并数组的下标)

代码

    // 合并两个有序数组
    int res = 0;
    void merge(vector<int>& arr, vector<int>& temp, int l, int m, int r) {

        int i = l, j = m + 1, k = 0;
        while (i <= m && j <= r) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
                // 奥妙之处
                //若 a[i] > a[j],则a[i] 和它后面的元素都大于 a[j]
                res += (m - i + 1);
                res %= 1000000007;
            }
        }
        while (i <= m) {
            temp[k++] = arr[i++];
        }
        while (j <= r) {
            temp[k++] = arr[j++];
        }

        // 将临时数组中的数据复制回原数组
        for (int p = 0; p < k; ++p) {
            arr[l + p] = temp[p];
        }
    }

// 归并排序函数
    void mergeSort(vector<int>& arr, vector<int>& temp, int l, int r) {
        if (l < r) {
            // 计算中间点
            int m = l + (r - l) / 2;

            // 递归地对左半部分和右半部分进行排序
            mergeSort(arr, temp, l, m);
            mergeSort(arr, temp, m + 1, r);

            // 合并已排序的两部分
            merge(arr, temp,l, m, r);
        }
    }
    int InversePairs(vector<int>& nums) 
    {
        //在外部开辟好辅助数组的空间
        //函数内部开辟的话,因为是递归式的调用,所以要多次构造和析构辅助数组
        //效率较低
        vector<int> temp(nums.size());
        mergeSort(nums,temp, 0, nums.size() - 1);
        return res;
    }

复杂度

时间复杂度:O( N l o g N NlogN NlogN),采用了归并排序的思路

空间复杂度:O(N), 借用了和原数组长度相同的辅助数组

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/609348.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【联通官网及APP注册/登录安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞 …

2024服贸会,参展企业媒体宣传报道攻略

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 2024年中国国际服务贸易交易会&#xff08;简称“服贸会”&#xff09;是一个重要的国际贸易平台&#xff0c;对于参展企业来说&#xff0c;有效的媒体宣传报道对于提升品牌知名度、扩大…

AI应用案例:运输车辆驾驶行为分析模型

随着道路交通的发展&#xff0c;运输行业车辆在数量增长的同时&#xff0c;交通事故也越发的频繁。据统计数据显示&#xff0c;2021年我国发生交通事故45万起&#xff0c;除了机动车本身的安全配置不高、车辆众多及我国路况复杂等客观原因外&#xff0c;从根本上讲&#xff0c;…

可视化数据大屏带你走进工业4.0

工业4.0是指第四次工业革命&#xff0c;是对工业生产的一种新的理念和模式。它通过将物理系统与数字系统相互连接&#xff0c;实现工业生产的智能化、自动化和网络化。工业4.0的核心目标是通过数字化技术和数据驱动的方法&#xff0c;实现生产过程的高度灵活性、效率和智能化。…

探索人工智能的深度神经网络:理解、应用与未来

深度神经网络&#xff08;DNNs&#xff09;是一种人工智能模型&#xff0c;其灵感来自于人脑神经元之间的连接。它们由多个层次组成&#xff0c;每一层都包含多个神经元&#xff0c;这些神经元通过权重连接在一起。信息通过网络的输入层传递&#xff0c;并经过一系列隐藏层&…

Verilog复习(二)| 时延

时延分为惯性延迟&#xff08;Inertial Delay (Gates) &#xff09;和传输延迟&#xff08;Transport Delay (Nets) &#xff09; 示例&#xff1a; wire #5 net_1; // 5 unit transport delayand #4 (z_out, x_in, y_in); // 4 unit inertial delay assign #3 z_out a &…

Windows安装RabbitMQ教程(附安装包)

需要两个安装包 Erlang 安装包: https://download.csdn.net/download/Brevity6/89274663 (自己从官网下载也可以) RabbitMQ Windows 安装包&#xff1a; https://download.csdn.net/download/Brevity6/89274667 (自己从官网下载也可以) Erlang安装 Erlang安装傻瓜式下一…

2024年想要开一家抖音小店,需要多少钱?一篇详解!

大家好&#xff0c;我是电商糖果 随着抖音卖货的持续火爆&#xff0c;抖音小店也成了电商行业讨论度最大的项目之一。 不少朋友都想知道&#xff0c;如果今年开抖音小店大概需要多少钱。 糖果做小店的时间也比较长&#xff0c;也经营了多家小店。 对于开一家抖音小店需要多…

蓝桥杯EDA客观题

目录 前言 一、PCB类知识点和题目分析 1.电阻 2.电容 3.封装类 4.单位转换类 5.电路板结构类 6.PCB绘制规则 7.立创软件 8.PCB硬件 线性电源和开关电源 二、数电知识点和题目分析 1.门电路 2.逻辑代数 3.组合逻辑电路 4.触发器 5.时序逻辑电路 6.其他 三、模…

java学习笔记反射机制

2.关于反射的理解 Reflection&#xff08;反射)是被视为动态语言的关键&#xff0c;反射机制允许程序在执行期借助于Reflection API取得任何 类的内部信息&#xff0c;并能直接操作任意对象的内部属性及方法。 框架 反射 注解 设计模式。 3.体会反射机制的“动态性” //…

vue3 - 图灵

目录 vue3简介整体上认识vue3项目创建Vue3工程使用官方脚手架创建Vue工程[推荐] 主要⼯程结构 数据双向绑定vue2语法的双向绑定简单表单双向绑定复杂表单双向绑定 CompositionAPI替代OptionsAPICompositionAPI简单不带双向绑定写法CompositionAPI简单带双向绑定写法setup简写⽅…

链表的中间结点(C语言)———链表经典算法题

题目描述. - 力扣&#xff08;LeetCode&#xff09;&#xff1a; ​ 答案展示: /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast,…

商业写字楼如何选择停车场管理系统?停车场管理系统建设有哪些注意事项

在现代商业环境中&#xff0c;写字楼停车场的高效管理对于维护企业形象、提高员工满意度以及增强客户体验至关重要。写字楼停车场管理的特点主要包括高流量、高周转率、多样化的车辆类型、高安全性要求以及对客户体验的重视&#xff0c;那么商业写字楼停车场应该从哪些方面提升…

【计网】TCP中的滑动窗口

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;日常聊聊 ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 正文 工作原理如下&#xff1a; 结语 我的其他博客 正文 TCP&#xff08;传输控制协议&#xff09;中的滑动窗口是一种用于流量控制和拥…

[Kubernetes] sealos部署 K8s 集群

文章目录 1.sealos 介绍2.操作系统基础配置3.安装部署 K8s4.验证 K8s 集群5.部署测试资源 1.sealos 介绍 Sealos 是一个基于 Kubernetes 内核的云操作系统发行版。它采用云原生方式&#xff0c;摒弃传统的云计算架构&#xff0c;转向以 Kubernetes 为云内核的新架构。这使得企…

30万奖励!2023-2024年度成都市工业企业“小升规”申报对象奖补、材料程序

一、申报对象及奖励标准 &#xff08;一&#xff09;2023年度申报对象及奖励标准。2022年3月1日至2022年12月31日首次进入成都市规模以上工业名录库的企业。2022年营业收入在2000万元&#xff08;含&#xff09;至5000万元的&#xff0c;给予10万元奖励&#xff1b;2022年营业…

4. 分布式链路追踪客户端工具包Starter设计

前言 本文将从零搭建分布式链路追踪客户端工具包的Starter&#xff0c;并将在后续文章中逐步丰富支持的场景。这里首先将搭建一个最基础的Starter&#xff0c;能提供的功能和1. 看完这篇文章我奶奶都懂Opentracing了一文中的示例demo类似。 相关版本依赖如下。 opentracing-…

大模型LLM之SFT微调总结

一. SFT微调是什么 在大模型的加持下现有的语义理解系统的效果有一个质的飞跃&#xff1b;相对于之前的有监督的Pre-Train模型&#xff1b;大模型在某些特定的任务中碾压式的超过传统nlp效果&#xff1b;由于常见的大模型参数量巨大&#xff1b;在实际工作中很难直接对大模型训…

视频剪辑批量转码技巧:如何将MP4视频快速转换为MP3音频的方法

在视频剪辑和音频处理的领域中&#xff0c;经常需要将视频文件转换为音频文件&#xff0c;特别是将MP4视频转换为MP3音频。这样的转换不仅可以减少文件大小&#xff0c;方便传输和存储&#xff0c;还可以在不损失音频质量的情况下&#xff0c;方便在各种设备上播放。下面&#…

AI写的论文AI疑似度太高怎么办?教你一招降低aigc痕迹

随着 AI 技术迅猛发展&#xff0c;各种AI辅助论文写作的工具层出不穷&#xff01; 为了防止有人利用AI工具进行论文代写&#xff0c;在最新的学位法中已经明确规定“已经获得学位者&#xff0c;在获得该学位过程中如有人工智能代写等学术不端行为&#xff0c;经学位评定委员会…