数组中的逆序对

题目描述

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

输入描述:

题目保证输入的数组中没有的相同的数字数据范围：  对于%50的数据,size<=10^4  对于%75的数据,size<=10^5  对于%100的数据,size<=2*10^5

示例 1

输入

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

输出

7

解题思路

• 把长度为 4 的数组分解成两个长度为 2 的子数组；

• 把长度为 2 的数组分解成两个长度为 1 的子数组；

• 把长度为 1 的子数组 合并、排序并统计逆序对 ；

• 把长度为 2 的子数组合并、排序，并统计逆序对。

如图所示，在计算完成子数组的逆序对合并之后，需要按照大小进行排序，以免在以后的统计过程中再重复统计。

子数组统计逆序对过程与合并过程如下图所示。

首先用两个指针指向数组末尾，比较两数字，如果第一个数组数字大，则构成逆序对，且数目等于第二个数组指针左边的数目（包括指针数字），否则不构成逆序对。较大值的指针在统计完逆序对后向左移动，并把较大值复制到新数组中的最右无值处。

代码

函数中 array 和 copy 互换是因为辅助数组只起到存储数组的作用，存储完后的数组在下一个迭代中才起作用，所以直接调换顺序更方便。

public class Solution {
  public int InversePairs(int [] array) {
      int length = array.length;
      if (length <= 0)
        return 0;
      int[] copy = new int[length];
      for (int i = 0; i < length; i++) {
        copy[i] = array[i];
      }
      long count  = InversePairsCore(array, copy, 0, length-1);
      return count % 1000000007;
  }
  
  private long InversePairsCore(int[] array, int[] copy, int start, int end) {
      if (start == end) {
        copy[start] = data[start];
        return 0;
      }
      int length = (end-start)/2;
      long left = InversePairsCore(copy, array, start, start+length);
      long right = InversePairsCore(copy, array, start+length+1, end);
    
      int i = start+length;
      int j = end;
      int indexcopy = end;
      long count = 0;
      while (i >= start && j >= start+length+1) {
        if (array[i] > array[j]) {
          copy[indexcopy--] = array[i--];
          count = count + j - start - length;
        } else {
          copy[indexcopy--] = array[j--];
        }
      }
      for (; i >= start; i--) {
        copy[indexcopy--] = array[i];
      }
      for (; j >= start+length+1; j--) {
        copy[indexcopy--] = array[j];
      }
      return left+right+count;
  }
}