示例 1:
输入: [7,5,6,4]
输出: 5
限制:
0 <= 数组长度 <= 50000
分析:
对于数组[7,5,6,4],若要计算其中的逆序对个数,及 [7,5],[7,6],[7,4],[5,4],[6,4],可以发现,若将所有逆序对依次交换其在数组中的位置,我们将会得到一个有序的数组,因此,我们可以用排序的思想来解决该题。
归并排序:
归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治策略(分治法将问题分成一些小的问题然后递归求解,而治的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。
归并排序是建立在归并操作上的一种有效的排序算法,归并排序对序列的元素进行逐层折半分组,然后从最小分组开始比较排序,合并成一个大的分组,逐层进行,最终所有的元素都是有序的
1.时间复杂度 归并排序算法每次将序列折半分组,共需要logn轮,因此归并排序算法的时间复杂度是O(nlogn)
2.空间复杂度 归并排序算法排序过程中需要额外的一个序列去存储排序后的结果,所占空间是n,因此空间复杂度为O(n)
3.稳定性 归并排序算法在排序过程中,相同元素的前后顺序并没有改变,所以归并排序是一种稳定排序算法
因此要求数组中的逆序对数,只需要计算通过归并排序,将数组中逆序对交换的次数即可。代码如下: