题解 | #数组中的逆序对# [P2]

mergeSort, 在merge的时候count reversePairs
请看 https://www.youtube.com/watch?v=kvXPpFP9sXg 这哥们儿讲的很清楚

public class Solution {
    public int InversePairs(int [] array) {
      if (array.length < 2) return 0;
      int[] tmp = new int[array.length];
      
      int ret = sortAndCount(0, array.length-1, array, tmp);
      return ret % 1000000007;
    }
  
    // sort array[l:r]
    int sortAndCount(int l, int r, int[] array, int[] tmp) {
      if (l == r) {
        return 0;
      }
      int m = l + (r-l)/2;
      int lPairs = sortAndCount(l, m, array, tmp) % 1000000007;
      int rPairs = sortAndCount(m + 1, r, array, tmp) % 1000000007;
      int lrPairs = mergeAndCount(l, m, r, array, tmp) % 1000000007;
      return lPairs + rPairs + lrPairs;
    }
  
    // array[l:m] and arry[m+1:r] are sorted.
    int mergeAndCount(int l, int m, int r, int[] array, int[] tmp) {
      for (int i = l; i <= r; i++) {
        tmp[i] = array[i]; // copy array[l:m] and arry[m+1:r] to tmp
      }
      int x = l, y = m+1;
      int count = 0;
      for (int i = l; i <= r; i++) {
        if (x > m) {
          array[i] = tmp[y]; 
          y++;
        } else if (y > r || tmp[x] <= tmp[y]) {
          array[i] = tmp[x]; 
          x++;
        }
        else {  // tmp[y] < tmp[x], have reversePairs
          array[i] = tmp[y];
          y++;
          // all remainings in array[l:m] forms a reversePair with tmp[y]
          count += m - x + 1;
        }
      }
      return count;
    }
}