题目描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。...例如7,5,4,6可以划分为两段7,5和4,6两个子数组
在7,5中求出逆序对,因为7大于5所以有1对
在6,4中求出逆序对,因为6大于4所以逆序对再加1,为2
对7,5和6,4进行排序,结果为5,7,...和4,6
设置两个指针分别指向两个子数组中的最大值,p1指向7,p2指向6
比较p1和p2指向的值,如果大于p2,因为p2指向的是最大值,所以第二个子数组中有几个元素就有几对逆序对(当前有两个元素,逆序对加...,逆序对加1,4+1=5,为5对,然后将5放入辅助数组,第一个子数组遍历完毕,只剩下第二个子数组,当前只有一个4,将4也放入辅助数组,函数结束。...辅助数组此时为4,5,6,7.逆序对为5.