蓝桥杯---归并排序2(leetcode170）题解

1.题目概述

逆序对时我们在线性代数里面学习行列式时候的一个概念，主要就是逆序，也就是后面的这个数字应该是比前面的这个数字小的，两个数字如果符合这个规律，组成的数对，就是一个逆序对，如果你学习过这个线性代数里面的行列式的相关内容，相信这个逆序对的概念对于你而言，也不是什么难以理解的事情；

而这个题目需要我们求解的就是这个里面的逆序对的个数，就是给定你一个数组，里面的任意两个元素进行组合，看看有多少种的组合是符合上面说的这个规律的，符合上述规律的这个数对的个数就是这个题目需要返回的数字；

2.示例讲解

上面的那个图片里面有一个实例：就是97546这个数组里面的元素，里面的这个逆序对的个数，并且虽然这个要求是返回数组的这个逆序对的个数，但是我们的这个题目的解释里面告诉了我们的这个对应的每一组都是什么，我认为这个是很容易理解的，上面也已经解释过了，比如他解释里面的97,95都是前面的这个数字比后面的这个数字大，这个就是逆序对；

说到这里，你会觉得，两个两个的进行组合，分别比较前面的和后面的数据大小关系，如果前面的比后面的大不就完了吗，但是这个暴力解决的方法肯定是超时的，所以我接下来会告诉大家:这个题目如何时候归并排序的思路，并且不会直接使用，而是告诉你这个思路是如何来的，因为这个题目本来就是困难题目，所以理解起来并不简单，但是不要忘了：待在舒适区，你永远长不大，只有做一些具有挑战性的东西，才可以学会成长，但是并不是让你只去抠难题，那样效果也不好，这个度如何把握，就只有我们大量练习才知道了；

其实我觉得这个和我们高中刷题很像：你只做自己会的题目，做起来肯定很清轻松，但是你不会有任何提升（可能提升就是提升你的熟练度，哈哈），但是如果你只去做压轴题，这个效果肯定也不好，对吧，这个时候你会如何去做，你应该大量刷题，知道题目的类型和对应的难度，你肯定是先思考，再看答案，发现答案也看不懂，这个时候就知道这个题目我目前阶段还做不出来，这个时候就抠了呗，做一些中档题目就行了，蓝桥杯也是如此，需要大量刷题，否则你连这个题目是难题还是简单题都看不出来；

3.思路分析

我们这个题目是使用的归并排序，但是如果一上来就是用这个方法，会有些难以理解，所以我们分为三个阶段逐步的引入；

想要明白这个题目，你必须对于这个归并排序的整体的思路和逻辑非常熟悉，这个是前提，否则你理解不了这个题目，所以我的建议就是你看这个题目的思路之前，去吧归并排序的思路和过程复习一下，否则你一会肯定看不懂（因为我就是这个样子的，先去听老师讲，后来发现听不懂，于是去重新复习了一下归并排序，再去看这个题目的讲解，反反复复，才明白了一点点）；

首先，想要扎到这个里面的逆序对的个数，我们的思路可以先在左边找出来这个逆序对的个数（mid左边）也就是把这个数组分为左半部分和右半部分，两边各自找出来逆序对之后，再一左一右进行寻找；

第二个层面就是左半部分和右半部分找完之后，各自进行排序处理，这个时候为什么要进行排序，其实是为了方便我们后续的这个一左一右处理的时候，当左右是经过排序的，一左一右找逆序对的时候就会提高一些这个查找的效率；

第一个策略：找出这个数据的前面，有几个比我大，这个针对的是升序处理的情况，为什么？

假设你的这个是降序处理的，这个时候数组里面，左右两边都是左边大右边小，看下里面的cur1和cur2，我们的这个cur1对应的数据大于cur2对应的数据的时候，符合上面说的找前面多少个数据比我（cur2下标对应的数据）大，但是这个时候cur1下一个位置的元素还有可能比我们的cur2对应位置的元素大，这个是不确定的（且涉及到重复计算的问题）；

但是当我们的排序之后是升序，这个时候左边小，右边大，这个时候cur1对应值小于cur2的时候，他一定是第一次小于cur2对应位置的数值，这个时候，因为我们要找的是前面比我大的数据的个数，因此这个时候cur1到mid的元素都是符合的，我们就可以直接计算；

第二个策略：选择一个数据，看看这个数据的后面，有几个比我小；
同理，这个时候必须要使用降序的逻辑，如果是升序的，cur2移动之后还有可能比cur1小，但是是降序的时候，cur1>cur2时，意味着我们的cur2后面的元素都是符合条件的，我们可以自己计算这个对应的个数；

4.代码分析

4.1策略一代码分析

这个里面的代码有相当一部分都是属于我们归并排序里面的逻辑，例如这个mid的确定，左右排序，最后的这个剩余的数据的挪动，都基本一致；

我主要解释一下：25到36行的代码的含义：首先就是双指针进行遍历，这个时候是升序处理，所以小元素放到这个temp数组里面去cur1<cur2意味着cur1对应的位置放到temp数组里面去，当前面大，也就是cur1大，后面小的时候,left和mid之间的都是符合条件的；ret统计这个符合条件的个数；

4.2策略2代码分析

策略二代码不变，就是这个排序的逻辑发生了变化，原来是升序，现在是降序，因此这个时候是谁大，谁放到这个temp数组里面去；但是我们的思路是后面多少比我小，应该是前面大，当遇到cur2对应的数据元素大的时候，直接放到temp里面去，cur1对应的元素大的时候，证明cur2小，所以这个时候cur2后面的元素都是符合条件的，加到这个ret里面即可；

5.我的总结

我认为这个题目确实不简单，需要我们理解这个归并排序的逻辑思路，需要掌握得很透彻，并且需要你画图进行分析，所以，需要我们不断的反思总结，细细品味，相信你的能力会有所提升~~

下面的这个是我创建的知识星球（免费加入），欢迎大家加入交流~~