【C++算法】48.分治_归并_数组中的逆序对

文章目录

    • 题目链接:
    • 题目描述:
    • 解法
    • C++ 算法代码:
    • 图解


题目链接:

剑指 Offer 51. 数组中的逆序对


题目描述:

bf1b557f6a2272923867b79316744c72


解法

解法一:暴力解法:暴力枚举

两层for循环

本题不能用,用了会超时。

解法二:

归并排序

c54f5e37f66b8dee89f4fb6dba821c7b


C++ 算法代码:

class Solution 
{int tmp[50010]; // 用于在归并过程中临时存储排序后的元素public:int reversePairs(vector<int>& nums) {return mergeSort(nums, 0, nums.size() - 1); //返回逆序对的数量}int mergeSort(vector<int>& nums, int left, int right){if(left >= right) return 0; // 基本情况:区间内只有一个元素或为空,没有逆序对int ret = 0; // 用于存储当前区间内的逆序对数量// 1. 找中间点,将数组分成两部分int mid = (left + right) >> 1; // 使用位运算 (left + right) / 2 提高效率// [left, mid][mid + 1, right]// 2. 递归地对左右两个子区间进行排序,并计算逆序对数量// 左边的个数 + 排序 + 右边的个数 + 排序 v // 右半部分的逆序对// 3. 计算跨越左右两个子区间的逆序对数量// cur1指向第一个子数组的当前元素// cur2指向第二个子数组的当前元素// i指向临时数组的当前位置int cur1 = left, cur2 = mid + 1, i = 0;// 当两个子数组都还有元素时,比较并处理while(cur1 <= mid && cur2 <= right) // 升序的时候{if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur1++];}else{// 当 nums[cur1] > nums[cur2] 时,说明 cur1 到 mid 之间的所有元素都大于 nums[cur2]// 因此,逆序对的数量为 mid - cur1 + 1ret += mid - cur1 + 1;tmp[i++] = nums[cur2++];}}// 4. 处理一下排序while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];// 5. 将临时数组中的合并结果复制回原数组的对应位置for(int j = left; j <= right; j++)nums[j] = tmp[j - left];return ret; // 返回当前区间内的逆序对总数}
};

图解

例如:nums = [9, 7, 5, 4, 6]

7f783442905ae0d00975ae6f42ad1b8c

  1. mergeSort(nums, 0, nums.size() - 1);->mergeSort(nums, 0, 4);

    ret = 0;mid = 2;

    ret += mergeSort(nums, left, mid);->ret += mergeSort(nums, 0, 2);

3309f512ac83b462e19c9b3a8eee59a6

  1. mergeSort(nums, 0, 2);

    ret = 0;mid = 1;

    ret += mergeSort(nums, left, mid);->ret += mergeSort(nums, 0, 1);

9624d3e24c19a45a8ddde35ef51d8e3a

  1. mergeSort(nums, 0, 1);

    ret = 0;mid = 0;

    ret += mergeSort(nums, left, mid);->ret += mergeSort(nums, 0, 0);

da07bddc53bd6f027b99b8dc0ae44d46

  1. mergeSort(nums, 0, 0);

    left = right -> return 0;

2ccef53a2b3792b7a6a65705f6ef7e77

  1. ret = 0;

    ret += mergeSort(nums, mid + 1, right);->ret += mergeSort(nums, 1, 1);

a3a116993342ebe207a789df1c181b74

  1. mergeSort(nums, 1, 1);

    left = right -> return 0;

c1404ba581d5063203b6ad151baa897e

  1. mergeSort(nums, 0, 1);

    ret = 0;mid = 0;

    cur1=0;cur2=1;i=0

    进入while循环

    ret += mid - cur1 + 1;->ret += 0- 0+ 1=1
    tmp[i++] = nums[cur2++];->tmp[0] = nums[1];->tmp[0]=7

    i=1;cur2=2,跳出while循环

    cur1<mid,tmp[i++] = nums[cur1++];->tmp[1] = nums[0];->tmp[1]=9

    i=2;cur1=1

    进入for循环

    nums[0]=7

    nums[1]=9

    return 1

    0f4a6e536834de2512abf1e2eb666a97

  2. mergeSort(nums, 0, 2);

    ret = 1;mid = 1;

    ret += mergeSort(nums, mid + 1, right);->ret += mergeSort(nums, 2, 2);

    4875e3302d5daa66e808568d83d4650e

  3. mergeSort(nums, 2, 2);

    left = right -> return 0;

    6313d64c80c2ca28b8fde3bd786e7fc5

  4. mergeSort(nums, 0, 2);

    ret = 1;mid = 1;

    cur1=0;cur2=2;i=0

    进入while循环

    ret += mid - cur1 + 1;->ret = ret + 1- 0+ 1=3
    tmp[i++] = nums[cur2++];->tmp[0] = nums[2];->tmp[0]=5

    i=1;cur2=3,跳出while循环

    cur1<=mid,tmp[i++] = nums[cur1++];->tmp[1] = nums[0];->tmp[1]=7

    i=2;cur1=1

    cur1<=mid,tmp[i++] = nums[cur1++];->tmp[2] = nums[1];->tmp[2]=9

    i=3;cur1=2

    进入for循环

    nums[0]=5

    nums[1]=7

    nums[2]=9

    return 3

    3513f7c729ea4a29588f43ca5fec3d45

  5. mergeSort(nums, 0, 4);

    ret = 3;mid = 2;

    ret += mergeSort(nums, mid + 1, right); ->ret += mergeSort(nums, 3, 4);

    78e4c6f18d6acf0f1dc1bd28fe55be88

  6. mergeSort(nums, 3, 4);

    ret = 3;mid = 3;

    ret += mergeSort(nums, left, mid);->ret += mergeSort(nums, 3, 3);

    28289b97440f6c1c878bebdff58d2d0c

  7. mergeSort(nums, 3, 3);

    left = right -> return 0;

    604208c48a4daa3ecbee819f4685796c

  8. mergeSort(nums, 3, 4);

    ret = 3;mid = 3;

    ret += mergeSort(nums, mid + 1, right);->ret += mergeSort(nums, 4, 4);

    dcf8a155909d2a4770cdce5737f3fa3c

  9. mergeSort(nums, 4, 4);

    left = right -> return 0;

    3a9d1646ceddd857b63f4586d5ebde39

  10. mergeSort(nums, 3, 4);

    ret = 3;mid = 3;

    cur1=3;cur2=4;i=0

    进入while循环

    tmp[i++] = nums[cur1++];->tmp[0] = nums[3];->tmp[0] = 4

    i=1;cur1=4,跳出while循环

    cur2<=right;tmp[i++] = nums[cur2++];->tmp[1] = nums[4];->tmp[1] = 6

    i=2;cur2=5

    进入for循环

    nums[3]=4

    nums[4]=6

    return 3

    4c2912cb7dbf9135797083dc13775aef

  11. mergeSort(nums, 0, 4);

    ret = 3;mid = 2;

    cur1=0;cur2=3;i=0

    进入while循环

    ret += mid - cur1 + 1;->ret = ret + 2- 0+ 1= 3 +3 =6
    tmp[i++] = nums[cur2++];->tmp[0] = nums[3];->tmp[0]=4

    i=1;cur2=4

    nums[cur1]<=nums[cur2];->tmp[i++] = nums[cur1++];->tmp[1] = nums[0];->tmp[1]=5

    i=2;cur1=1

    ret += mid - cur1 + 1;->ret = ret + 2- 1+ 1= 6 +2 =8
    tmp[i++] = nums[cur2++];->tmp[2] = nums[4];->tmp[2]=6

    i=3;cur2=5

    跳出while循环

    cur1=1,cur2=5

    cur1<=mid,tmp[i++] = nums[cur1++];->tmp[3] = nums[1];->tmp[3]=7

    i=4;cur1=2

    cur1<=mid,tmp[i++] = nums[cur1++];->tmp[2] = nums[2];->tmp[4]=9

    i=5;cur1=3

    进入for循环

    nums[0]=4

    nums[1]=5

    nums[2]=6

    nums[3]=7

    nusm[4]=9

ea7931050b984e5cd278e82fac8230c2

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

少样本学习之CAML算法

上下文感知元学习&#xff08;Context-Aware Meta-Learning, CAML&#xff09; 概述 在机器学习和深度学习领域&#xff0c;元学习&#xff08;Meta-Learning&#xff09;旨在通过学习如何学习&#xff0c;使模型能够在面对新任务时快速适应。传统的元学习方法通常需要在特定…

【ChatGPT】解锁AI思维链:如何让机器像人类一样思考?

在人工智能领域&#xff0c;我们一直在追求让机器像人类一样思考。然而&#xff0c;即使是最先进的AI&#xff0c;也常常被诟病缺乏“常识”&#xff0c;难以理解复杂问题&#xff0c;更不用说像人类一样进行逻辑推理和解决问题了。最经常的表现就是遇到不会的地方&#xff0c;…

leetcode 面试经典 150 题:长度最小的子数组

链接长度最小的子数组题序号209题型数组解题方法滑动窗口难度中等 题目 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl1, …, numsr-1, numsr] &#xff0c;并返回其长度。如果不存在符合条件…

多进程并发跑程序:pytest-xdist记录

多进程并发跑程序&#xff1a;pytest-xdist记录 pytest -s E:\testXdist\test_dandu.py pytest -s testXdist\test_dandu.py pytest -s &#xff1a;是按用例顺序依次跑用例 pytest -vs -n auto E:\testXdist\test_dandu.py pytest -vs -n auto&#xff0c;auto表示以全部进程…

Vue2二、指令补充,computed 计算属性vs方法,watch 侦听器,

一、指令补充 1.修饰符。2.动态操作class。3.动态操作style。4.v-model 用于其他表单元素 1.修饰符 ① 按键修饰符 keyup.enter → 键盘回车监听 <body><div id"app"><h3>keyup.enter → 监听键盘回车事件</h3><input v-model"…

spring\strust\springboot\isp前后端那些事儿

后端 一. 插入\更新一条数据&#xff08;老&#xff09; Map<String, Object> parameterMap MybatisUtil.initParameterSave("Send_ProjectFrozenLog", sendProjectFrozenLog); commonMapper.insert(parameterMap);parameterMap MybatisUtil.initParameter…

uniapp连接蓝牙操作(蓝牙设备地锁)

介绍&#xff1a; 本文采用uni-app框架来创建一个简单的用户界面&#xff0c;用于搜索、连接和发送命令给蓝牙设备。 1.打开蓝牙适配器 function openBluetooth() {uni.openBluetoothAdapter({success() {uni.offBluetoothDeviceFound();// 监听新设备发现事件uni.onBlueto…

安防监控Liveweb视频汇聚融合平台助力执法记录仪高效使用

Liveweb平台可接入的设备除了常见的智能分析网关与摄像头以外 &#xff0c;还可通过GB28181协议接入执法记录仪&#xff0c;实现对执法过程的全程监控与录像&#xff0c;并对执法轨迹与路径进行调阅回看。那么&#xff0c;如何做到执法记录仪高效使用呢&#xff1f; 由于执法记…

10 JVM内置锁

我们先想明白一个问题&#xff0c;什么是锁&#xff1f; 我们去给自己家锁门的时候&#xff0c;只有对应的一把钥匙能开锁。当用钥匙去开锁的时候&#xff0c;锁孔的内置型号会验证钥匙能不能对的上。能对上就能把锁打开&#xff0c;然后进到家里使用家里的资源。否则就在外面等…

建立在商用GPT上的简单高效单细胞表示模型

大规模基因表达数据正被用于单细胞表示模型的预训练。然而&#xff0c;这样的模型需要大量的数据管理和训练。在这里&#xff0c;作者探索了一种更简单的替代方案&#xff1a;使用 GPT-3.5 从单个基因的文本描述中生成基因嵌入&#xff0c;然后通过基因表达量加权gene embeddin…

tryhackme-Pre Security-Defensive Security Intro(防御安全简介)

任务一&#xff1a;Introduction to Defensive Security防御安全简介 此room的两个要点&#xff1a; Preventing intrusions from occurring 防止入侵发生Detecting intrusions when they occur and responding properly 检测发生的入侵并正确响应 防御安全还有更多内容。 除上…

[Unity] Text文本首行缩进两个字符

Text文本首行缩进两个字符的方法比较简单。通过代码把"\u3000\u3000"加到文本字符串前面即可。 比如&#xff1a; 效果&#xff1a; 代码&#xff1a; TMPtext1.text "\u3000\u3000" "选择动作类型&#xff1a;";

Python:Matplotlib详细使用

1.Matplotlib简介 Matplotlib是python数据分析三剑客之一&#xff0c;是一个功能强大且非常流行的Python数据可视化库。Matplotlib可用于绘制折线图(line plot)、散点图(scatter plot)、条形图(bar plot)、直方图(histogram plot)、饼图(pie plot)等&#xff0c;同时也支持部分…

MIT S6081 2024 Lab 1 | Operating System | Notes

目录 安装与下载 实验1 开始我们的实验 sleep&#xff08;简单&#xff09; pingpong&#xff08;简单&#xff09; primes (中等)/(困难) find&#xff08;中等&#xff09; xargs&#xff08;中等&#xff09; finally Reference I. Tools Debian 或 Ubuntu Arch…

【Java】mac安装Java17(JDK17)

文章目录 下载java17一、安装二、环境变量 下载java17 官网下载&#xff1a;https://www.oracle.com/java/technologies/downloads 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、安装 直接安装后&#xff0c;安装完后目录会存放在下面目录下 /…

【USB-HID】“自动化键盘“

这里写目录标题 【USB-HID】"自动化键盘"1. 前言2. 框架3. 实现3.1 模拟键盘按键输入 【USB-HID】“自动化键盘” 1. 前言 最近从朋友那了解了一种"自动化键盘"&#xff0c;能够通过上位机录制按键脚本&#xff0c;然后执行脚本&#xff0c;实现物理键盘…

XXE靶机漏洞复现通关

1.扫描XXE靶机的ip地址 将kali虚拟机和XXE靶机部署在同一局域网中&#xff0c;都采用NAT网络模式 搭建好后在kali终端中进行扫描XXE靶机的ip arp-scan -l 根据常识我们可以推断192.168.27.153为靶机的ip地址 2.访问靶机页面并扫描附录 进入页面后我们可以打开御剑扫描网页中…

leetcode 36.有效的数独

1.题目要求: 2.题目步骤: 写好判断函数 3.题目代码: class Solution { public:bool isvalid(vector<vector<char>>& board,char num,int row,int col){//先找左下标int leftrow row - 1;while(leftrow > 0){if(board[leftrow][col] num){return fals…

在C#中测试比较目录的不同方法以查看它们有哪些共同的文件

C# 中的示例“比较目录以查看它们有哪些共同的文件”使用Directory.GetFiles获取两个目录中的文件。它对文件进行排序&#xff0c;并比较两个排序后的列表以查看哪些文件位于第一个目录中、第二个目录中或两个目录中。有关其工作原理的详细信息&#xff0c;请参阅该示例。 Kur…

【Java基础面试题019】什么是Java中的不可变类?

回答重点 不可变类是指在创建后无法被修改的类。一旦对象被创建&#xff0c;它的所有属性都不能被更改。这种类的实例在整个生命周期内保持不变。 关键特征&#xff1a; 声明类为final&#xff0c;防止子类继承类的所有字段都是private和final&#xff0c;确保它们在初始化后…