(算法)统计逆序对

题意

逆序对,如果前面的元素大于后面的元素则为一个逆序对,统计一个数组中逆序对的个数并返回

思路

思路:每次遇到左半边数组的元素大于右边数组元素,说明产生逆序对

产生逆序对的个数为:(mid - 左边数组元素当前下标 + 1)。说明有这么多个元素是大于当前右边数组这个元素。

一句话总结就是:如果右半部分数组当前元素小于左半部分数组的当前元素,那么当前左半部分数组的当前元素后面的元素(包括当前元素)都是大于右半部分数组当前元素的,也就是统计左半部分数组当前元素后面元素(包括当前元素)有多少个即可。

例如:左半部分数组为1,3,4 右半部分数组为1,2,5
那么如果当前左半部分数组元素为3,右半部分数组当前元素为2,此时产生的逆序对便是左半部分数组元素3右边所有的元素(包括3这个元素)

算法

(算法)小和问题

使用归并排序来对小和问题进行求解

步骤

因为归并排序已经将数组分成了两个已经有序的子数组,我们要想统计小和的个数,我们就需要在merge的过程中统计小和的个数。

假设本次要merge两个子数组为num1, num2。分别为num的左右两个子数组,其中num1的下标从0到mid,num2的下标从mid+1到right

  1. 如果每次合并的时候num2中的元素num2[j]小于num1中的元素num1[i],此时会产生小和
    1. 对于num1中的元素num1[i],此时比它大的有num2中的第j个元素之后的所有元素(包括num2的第j个元素)。这里我们不考虑num1中比num1[i]大的元素,因为我们在生成有序num1的时候就已经考虑过了。
    2. 所以此时num2中大于num1[i]元素个数为(r-j+1),但是要统计小和,所以我们让之前统计小和的结果加上(r-j+1)* num1[i]
    3. 不断循环,知道整个数组都已经归并完成
  2. 上面第1步是合并了num的从l到j的元素,但是我们还要不断递归

几个关键点

  1. return mergeSort(nums, l, mid) + mergeSort(nums, mid+1, r) + merge(nums, l, mid, r) 这里是我们统计左边半个数组内部的小和以及右边半个数组内部的小和,以及左右两个子数组合并时候产生的小和

  2. ret += (r-j+1) * nums[i] 因为是要求小和,所以我们统计出了比num[i]小的元素个数为(r-j+1)个,最后还是要乘以nums[i]来获取nums[i]的两个数组之间的小和

算法

归并排序

应用场景

  1. 求小和
  2. 求逆序对的个数

几个注意点:

mid := l + (r-l)>>1 避免数组越界

for i <= mid { help[index] = nums[i] index++ i++ },这里是一个for循环,不是if,因为是要将后面剩下的数拷贝进来

for i <= mid { help[index] = nums[i] index++ i++ },这里是一个for循环,不是if,因为是要将后面剩下的数拷贝进来