1.归并排序912. 排序数组 - 力扣LeetCodehttps://leetcode.cn/problems/sort-an-array/description/归并排序核心思想也是用递归实现的给了一个数组首先选一个中间点mid根据中间点mid 把数组分成了两部分。然后先把左边部分排序排序时相当于又是一个归并还是选个中间点再把数组划分为两部分。继续排左边部分当数组只有一个元素时向上返回。当左边排序后去右边排序排完返回后合并两个有序数组最终不断返回左边就排完了然后右边同样的方法下面来实现2.数组中的逆序对LCR 170. 交易逆序对的总数 - 力扣LeetCodehttps://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/先说一下暴力解法依次固定一个数在这个数后面区间找有多少个数比这个数小就可以了(但会超时)。于是又想了一个策略数组分为两部分左半部分找逆序对右半部分找逆序对再一左一右找逆序对这些结果合起来。再把这个策略扩展一下左半部分挑完逆序对后进行左排序右半部分挑完逆序对后进行右排序然后再一左一右挑挑完再排(结合递归)。有了上述铺垫则可利用归并排序解决该问题左半部分挑/左挑左边排可在递归中完成右半部分挑/右挑右排可在递归中完成核心是搞定一左一右/一左一右排。这本质还是暴力找为啥加了排序后就变快了到第三步时两边已经有序了假设此时左右两边刚好遍历到cur1和cur2它们左边的元素都要比它们本身小。策略一是找出该数之前有多少个数比我大此时盯着cur2看因为前大后小完美契合归并排序步骤(NlogN)。那用降序可以解决吗若nums[cur1]nums[cur2]统计完后cur1可能照样大会重复统计所以策略一不能用降序。策略二找出该数之后右区域有多少个数比我小(降序)若是升序又会重复计算所以用降序弄完cur1右移。(结合实际问题想)下面来实现3.计算右侧小于当前元素的个数315. 计算右侧小于当前元素的个数 - 力扣LeetCodehttps://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/用归并来解决这道题要求出当前元素右边有多少个比我小应该用上一套题中的策略二(降序)。大逻辑是想搞定整个数组的最终结果先把它弄成两部分先把左边部分结果找到再把右边部分结果找到再左选一个右选一个就能把所有的结果找到。接下来分析一左一右的情况若nums[cur1]nums[cur2]---cur2若nums[cur1] nums[cur2]---把right-cur21的结果放在原始下标所对应的位置上那如何找到排完序后nums中当前元素的原始下标是多少呢弄个index数组表示最初nums数组的原始下标不管归并的时候nums怎么变让两个元素绑定移动这样就能找找到原始下标了。下面来实现4.翻转对493. 翻转对 - 力扣LeetCodehttps://leetcode.cn/problems/reverse-pairs/description/题目意思是找两个数保证前面一个数大于后面一个数的两倍。暴力解法就是固定一个数依次枚举后面的数。解法二是和逆序对的方法类似先求求左边部分再求右边部分然后再一左一右。逆序对那里是nums[i]nums[j]这里要求nums[i]2nums[j]所以不能按归并排序里的流程求翻转对了。策略一计算当前元素后面有多少个元素的两倍比我小这用降序要找当前元素后面则要盯着cur1让cur2走看有多少个两倍比cur1小。若cur2位置两倍大的话让cur2右移发现2倍比cur1小的时候此时可统计出right-cur21这么多元素此时cur1右移cur2不用回来判断因为降序那部分肯定不符合(直到cur1或cur2走完)策略二计算当前元素之前有多少元素的一半比我大这用升序。盯着cur2看让cur1开始找若cur1的一半比cur2小则cur1右移。当移到某处发现cur1的一半比cur2大则后面都是大的此时可统计统计完cur2右移cur1不用回退前面也不符合cur1继续向右走判断。接下来还要合并两个有序数组这道题和之前区别是不能利用合并两个有序数组逻辑来计算翻转对因为这的判断条件是nums[i]2nums[j]。下面实现(降序版)若乘法溢出这样改升序这样改