题目
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。 并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字 数据范围： 对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5
分析
最直观的思维就是从前往后，每次取数组的一个数，然后将这个数和它之后的的每一个数进行比较，如果大于他之后的数，总数就+1.
这个方法取每个数字，要取n次，比较也要n次，因此时间复杂度是O(n2)。
其实这个题，是归并排序的变种，并且只是需要在每次排序的时候，假如左边的元素比右边的元素大，那么左右两边的数组本来就是升序，假如左边数组的当前指针 索引是leftIndex，右边数组的当前指针是rightIndex，那么从leftIndex+1到mid,这之间的数都是大于leftIndex指向的数，mid+1到rightIndex-1之间的数都是 小于rightIndex指向的数的。
因此，如果左边数组的leftIndex > 右边数组的rightIndex。那么左边数组一定是大于mid+1指向的数，因此个数就是mid+1-leftIndex
至于详细的归并排序，可以参考我的排序算法的博客。
代码
public class Solution {
int count;
public int InversePairs(int[] array) {
count = 0;
if (array != null || array.length == 0)
mergeSort(array, 0, array.length - 1);
return count%1000000007;
}
public void mergeSort(int[] a, int left, int right) {
if (left >= right)
return;
int mid = (left + right) >> 1;
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
public void merge(int[] a, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int leftIndex = left;
int rightIndex = mid + 1;
int tempIndex = 0;
while (leftIndex <= mid && rightIndex <= right) {
if (a[leftIndex] <= a[rightIndex])
tmp[tempIndex++] = a[leftIndex++];
else {
tmp[tempIndex++] = a[rightIndex++];
count += mid - leftIndex + 1;
count%=1000000007;
}
}
while (leftIndex <= mid)
tmp[tempIndex++] = a[leftIndex++];
while (rightIndex <= right)
tmp[tempIndex++] = a[rightIndex++];
for (tempIndex = 0; tempIndex < tmp.length; tempIndex++)
a[left + tempIndex] = tmp[tempIndex];
}
}
