leetcoad链接:https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/
视频链接:https://www.algomooc.com/1290.html
涉及知识点:归并排序计算逆序数+索引数组
方法一:采用暴力解法:(暂时没有提供)

方法二:采用归并排序的思路:

  1. 采用了归并排序的思路
  2. 在归并排序的时候的合并的过程中会去统计相应的逆序对数(也是这道题的难点所在)
  3. 需要知道合并之后的数字在原来的数组中是在什么位置(需要通过索引数组来进行查找)
  4. 将元素nums[i]与元素的索引位置建立一个索引(数字无论怎么移动,相应的索引位置却是不会变的
  5. 对数组进行归并排序操作
    * 对有逆序对数的情况进行+1的操作(由于前面已经将下标与元素值进行了一一的绑定,所以能够很快的对count进行操作的位置)
    * index[i]:表示nums中索引为i的那个数
  6. 一个重要的判断入口:判断左区间最右边的元素是否大于右区间最左边的元素
  7. 子序列排序并统计(也就是这道题需要另外的再编写的一个函数,也是题目中的一个关键点)
    • 创建了一个新的数组aux(创建的目的是:只是为了复制index数组中的值):也是问吴师兄的一个关键点
      • 设置两个变量来记录一下
      • 【 mid + 1,right 】这个区间的所有元素都访问完毕,这个区间总共有 right - mid 个元素(这里再结合图解好好的理解清楚再继续的今进行下去)这些数字都是i指向的那个元素的逆序数
      • counter[i]:表示索引位置为i的那个数字有多少个逆序对数
ToTOP