题目描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。...size<=2*10^5
示例1
输入
1,2,3,4,5,6,7,0
输出
7
解题思路
很容易想到的方法就是遍历每一个元素,让其与后面的元素对比,如果大于则count++,但是这样的时间复杂度是...例如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指向的是最大值,所以第二个子数组中有几个元素就有几对逆序对(当前有两个元素,逆序对加...,所以子数组中没有能和当前p2指向的6构成逆序对的数,将p2指向的值放入辅助数组,并向前移动一位指向4,此时辅助数组内为6,7
继续判断p1(指向5)和p2(指向4),5>4,第二个子数组中只有一个数字