(算法)小和问题

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

步骤

因为归并排序已经将数组分成了两个已经有序的子数组,我们要想统计小和的个数,我们就需要在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]的两个数组之间的小和

算法