## 描述

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

## 思路

merge sort

写了很久，其实没什么难的

## 代码

```c++

class Solution {

public:

int res;

// l inclusive, r exclusive

void mergesort(vector & data, int l, int r) {

// if only one element left, return

if (l + 1 >= r) return;

int m = (l + r) / 2;

mergesort(data, l, m);

mergesort(data, m, r);

// now left and right are sorted

int i = l, j = m;

while (i < m and j < r) {

if (data[i] > data[j]) {

res += m - i; // add

res %= 1000000007;

j ++ ;

} else

i ++ ;

}

// sort the entire vector

vector buf (r - l, 0);

i=l;

j=m;

int idx = 0;

for(; i

buf[idx] = data[i]

while (i

while (j

for(int i=l;i

data[i] = buf[i-l];

}

int InversePairs(vector data) {

mergesort(data, 0, data.size());

return res;

}

};

```

一键复制

编辑

Web IDE

原始数据

按行查看

历史