蓝桥杯---归并排序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.我的总结

我以为这个标题确实不简朴，必要我们明确这个归并排序的逻辑思绪，必要把握得很透彻，而且必要你绘图举行分析，以是，必要我们不绝的反思总结，细细咀嚼，信任你的本领会有所提拔~~
下面的这个是我创建的知识星球（免费参加），欢迎各人参加交换~~