【归并分而治之】逆序对的应对之策

2024-09-04 04:20

本文主要是介绍【归并分而治之】逆序对的应对之策,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

目录

  • 1.前言
  • 2.题目简介
  • 3.求解思路
    • 为什么要这样做?
    • 快在哪?
    • 为什么这种方法会想到结合归并排序?
    • 如何在一左一右中统计剩下的逆序对个数?
    • 固定右边的数,用降序会怎么样???
    • 思路的本质是巧妙地结合了归并的思想
  • 4.示例代码

1.前言

今天了解到一种比较有意思的题目解法,是专门针对逆序对的。下面来进行简单分享。

2.题目简介

题目链接:LINK
在这里插入图片描述

3.求解思路

我们一种解法是暴力求解,当然还有一种就是利用归并排序的思想
下面我们着重来讲解归并排序这个求解思路。

首先,我们把统计整个序列分成两块,一左一右。我们首先单统计一下左边这块区域能够满足我们条件的逆序对数量,再统计一下右边这块区域能够满足我们条件的逆序对数量,之后再一左一右去统计剩下的逆序对数量,这样加起来就跟暴力求解一样了。
在这里插入图片描述

但是在这其中加上排序之后,结合归并排序的分治思想,可以更快。

为什么要这样做?

在这里插入图片描述

快在哪?

快就快在每次处理一左一右的逆序对个数的时候,因为我们是排好序的,所以可以快速统计。

为什么这种方法会想到结合归并排序?

因为这个思想非常贴近归并排序。

如何在一左一右中统计剩下的逆序对个数?

在这里插入图片描述
在这里插入图片描述
如果固定右边的数,那就得用升序
如果固定左边的数,那就得用降序

固定右边的数,用降序会怎么样???

如果固定右边的数,用降序,会出错,因为会统计到一些重复的逆序对。
在这里插入图片描述

固定左边的数,用升序也会有上面问题,是相同的道理的。

思路的本质是巧妙地结合了归并的思想

整体的话我感觉这个解题思路就是巧妙地结合了归并排序,然后就弄出了这么个方法。

4.示例代码

class Solution {
public:
//升序,向前找大int tmp[50001];int reversePairs(vector<int>& nums) {//利用归并分而治之的思路来解决问题return mergeSort(nums, 0, nums.size() - 1);}int mergeSort(vector<int>& nums, int left, int right){//只有一个数字或者不存在的区间直接返回0if(left >= right){return 0;}//左边的个数、右边可以匹配的个数,顺便进行排序int mid = (left + right) / 2;int ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);//一左一右的匹配对数int cur1 = left, cur2 = mid + 1, i = left;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur1++];}else{ret += mid - cur1 + 1;tmp[i++] = nums[cur2++];}}//继续处理排序,前面只做了一部分while(cur1 <= mid){tmp[i++] = nums[cur1++];}while(cur2 <= right){tmp[i++] = nums[cur2++];}//把数据写回原数组for(int j = left; j <= right; j++){nums[j] = tmp[j];}return ret;}
};

在这里插入图片描述


EOF

这篇关于【归并分而治之】逆序对的应对之策的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1134982

相关文章

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客,我们学习了排序算法中的插入排序和选择排序,接下来我们将继续探索交换排序与归并排序,这两个排序都是重头戏,让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换,让较大的元素逐渐向右移动,从而将最大的元素移动到最右边。 动画演示: 1.1.2 具体步

面对Redis数据量庞大时的应对策略

面对Redis数据量庞大时的应对策略,我们可以从多个维度出发,包括数据分片、内存优化、持久化策略、使用集群、硬件升级、数据淘汰策略、以及数据结构选择等。以下是对这些策略的详细探讨: 一、数据分片(Sharding) 当Redis数据量持续增长,单个实例的处理能力可能达到瓶颈。此时,可以通过数据分片将数据分散存储到多个Redis实例中,以实现水平扩展。分片的主要策略包括: 一致性哈希:使用一

归并排序/计数排序

1:归并排序 1.1:代码 void _MergeSort(int* arr, int left, int right, int* tmp){if (left >= right){return;}int mid = (left + right) / 2; _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid+1, righ

逆序和顺序创建单链表

单链表是一种顺序的存储方式,数据结构学的不好,考研又是必考内容,只好从头开始学习,相信不断地积累会有更好的爆发! 首先单链表的创建,单链表是建立在结构体的基础上,要创建单链表首先要建立起一个储存数据的结构体: struct node{int elem;node *next;};elem是数据域,用来存放你要输入的数据,next是指向下个存放数据节点的指针同为node 类型; 下面是

【Hdu】Minimum Inversion Number(逆序,线段树)

利用线段树在nlogn的时间复杂度内求一段数的逆序。 由于给的序列是由0 ~ n -1组成的,求出初始的逆序之后可以递推出移动之后的逆序数。 #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const in

【SGU】180. Inversions(归并排序求逆序数)

以前一般用树状数组和线段树做这种题 这次换个思路试试,归并排序! #include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 111111;int n;int array[maxn];int tmp[maxn];L

【redis】数据量庞大时的应对策略

文章目录 为什么数据量多了主机会崩分布式系统应用数据分离架构应用服务集群架构负载均衡器数据库读写分离 引入缓存冷热分离架构 分库分表微服务是什么代价优势 为什么数据量多了主机会崩 一台主机的硬件资源是有上限的,包括但不限于一下几种: CPU内存硬盘网络… 服务器每次收到一个请求,都是需要消耗上述的一些资源的~~ 如果同一时刻处理的请求多了,此时就可能会导致某个硬件资源不够用了

分库分表:应对大数据量挑战的数据库扩展策略

随着互联网技术的发展,数据量的爆炸性增长给数据库系统带来了前所未有的挑战。为了有效管理大规模数据并保持高性能,分库分表成为了一种常见的数据库扩展策略。本文将探讨分库分表的概念、动机、实施策略以及潜在的挑战和解决方案。 什么是分库分表? 分库分表是一种数据库架构设计策略,它将数据分散存储在多个数据库(分库)和多个表(分表)中。这种方法可以提高数据库的可伸缩性、可用性和性能。 为什么需要分库分表

教你如何应对算法备案难点以及备案后应该做什么?

教你如何应对算法备案难点以及备案后应该做什么? 自去年六月至今年八月,网信办已公布七批备案清单,共计1919项算法成功备案,标志着算法备案步入常态。主体备案虽门槛较低,算法备案却考验专业,尤其是《算法安全自评估报告》成为监管焦点,逾百项审查要点需逐一回应。算法数据的输入输出、模型架构、训练数据、策略逻辑与风险管理,每一环皆需详尽说明。下面,小编给大家着重讲讲互联网算法备案申请的难点以及备案

归并排序-非递归实现

归并排序的非递归实现  我们可以把 一个数组 先拆分成 最小单元,这是分, 拆分成最小单元之后,我们对每个最小单元进行一次合并,这是治 最小单元 合并一次之后,我们继续 在上一次合并的基础上拆分,并且合并这是 合 , 直到 整个数组 只被拆成了两部分,在进行最终一次的和   我们画图举个例子 源代码如下,我们的merge的合并函数的参数是  原数组,左侧小数组索引位置开头,左侧小数