分治
。 我们进行一次归并排序,并在归并过程中计算逆序数,换句话说 逆序对是归并排序的副产物
。如果不熟悉归并排序,可以先查下相关资料。 如果你直接想看归并排序代码,那么将的代码统计 cnt 部分删除就好了。
为了方便描述,我将题目中的:i < j such that nums[i] > nums[j] * 3,改成 i < j such that nums[i] > nums[j]。也就是将 3 倍变成一倍。 如果你理解了这个过程,只需要比较的时候乘以 3 就行,其他逻辑不变。
i
,j
指针如粗体部分(左数组的 3 和右数组的 2)。 那么 逆序数就是 mid - i + 1
也就是 3 - 2 + 1 = 2
即(3,2)
和 (4,2)
。 其原因在于如果 3 大于 2,那么 3 后面不用看了,肯定都大于 2。 ️ 之后会变成:[1,2,3,4] 右:[2,5] (左数组的 3 和 右数组的 5),继续按照上面的方法计算直到无法进行即可。