数组中的逆序对 牛客网 剑指Offer

数组中的逆序对 牛客网 剑指Offer

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P00000007

输入描述:

题目保证输入的数组中没有的相同的数字

数据范围：

对于P的数据,size<=10^4

对于u的数据,size<=10^5

对于0的数据,size<=2*10^5

示例1

输入

复制

1,2,3,4,5,6,7,0

输出

复制

7

class Solution { public: //run:141ms memory:4944k int InversePairs(vector<int> data) { if(data.size() == 0){ return 0; } vector<int> copy; for(int i = 0; i < data.size(); ++i){ copy.push_back(data[i]); } return InversePairsCore(data, copy, 0, data.size() - 1) % 1000000007; } long InversePairsCore(vector<int> &data, vector<int> ©, int begin, int end){ if(begin == end){ copy[begin] = data[end]; return 0; } int mid = (end + begin) >> 1; long leftCount = InversePairsCore(copy, data, begin, mid); long rightCount = InversePairsCore(copy, data, mid + 1, end); int i = mid; int j = end; int indexcopy = end; long count = 0; while(i >= begin && j >= mid + 1){ if(data[i] > data[j]){ copy[indexcopy--] = data[i--]; count += j - mid; } else{ copy[indexcopy--] = data[j--]; } } for(;i >= begin; --i){ copy[indexcopy--] = data[i]; } for(;j >= mid + 1; --j){ copy[indexcopy--] = data[j]; } return leftCount + rightCount + count; } };

转载于:https://www.cnblogs.com/vercont/p/10210375.html