蓝桥杯---归并排序4（leetcode493）题解

1.题目重述

这个题目的要求是需要我们去找到这个翻转对，这个反转对实际上就是前面的数据是后面的这个数据的两倍，这个时候我们就让这两个数据进行位置的交换即可；

最后的这个返回值就是我们的这个翻转对的数量，也就是我们的这个数组里面满足前面的数据是后面数据两倍的这个组数；

2.思路分析

这个还是分为降序和升序两个情况：还是使用的cur1,cur2进行这个比较的过程的，因此下面开始进行分析；

• 降序：计算这个元素的后面，多少个元素的两倍是比我小的；

这个里面还涉及到一个不等式和双指针不回退的逻辑，不知道大家是不是可以尝试分析出来这个过程，就是我们的这个策略一里面是后面多少个元素的两倍比我小，当我们的这个cur2满足条件之后，本来我们的cur1向后移动，我们的这个cur2应该是回退到起点的位置继续进行比较和判断的，但是实际上我们的这个cur2指针实际上是必须要会退的，如果你经过分析，因为我们的这个cur2前面的元素的两倍都是比这个cur1位置的元素大的，这个时候我们的cur1向后面进行移动，这个数组是降序的，意味着什么是不是我们的这个元素变小了，人间的cur2前面的元素都比你cur1大了，你现在是cur1后面的元素，因此这个时候cur2前面的元素肯定是比你大的（这个就是我们的不等式的逻辑，我简单的进行了描述，希望大家可以理解）

• 升序：当前的元素的前面，多少个元素的一半还是比我大的；

上面的那个策略一里面使用大片的逻辑说明了这个不等式比较，我们的这个指针不需要进行回退的这个原理和具体的逻辑，下面的这个其实也是一样的道理，就是我们的这个cur1在这个cur2移动的过程中是不需要进行回退操作的；（大家可以自行尝试按照上面的逻辑理解一下，原理完全一致）；

3.代码分析

降序版本：降序和升序里面有些内容是不变的，就是我们的这个区间的划分和里面进行排序的这个逻辑有所区别罢了；

降序的话，这个统计的就是当前元素的后面，多少个元素的两倍是比我小的，并且在这个过程里面时刻牢记这个数组进行归并过程里面进行排序的时候是降序的，这个很重要，这个决定了我们到时候进行这个不等式判断这个满足条件的元素的个数的时候会派上用场；

首先按照上面说的这个思路，cur2需要不断的去进行移动，ret加上的就是这个过程里面的满足条件的个数里面嵌套的这个while实际上说的就是cur2指向的元素大，这个时候把他放到我们的这个归并数组里面去即可，因为时刻牢记这个是降序的；

32行的三目就是谁大谁就往这个归并数组的前面放置即可

升序版本：

时刻牢记这个数组是升序的，找的是前面的元素的一半还是比我大的，因此这个时候cur2是不动的，控制这个循环cur2大的话，这个时候cur1++,否则就是这个cur1位置的数据大，这个时候因为升序，所以这个时候就是cur1后面的元素都是满足条件的；

最后32行里面的那个就是三目：谁小谁就放到这个数组里面的前面去即可；