题目
在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组，求出这个数组中的逆序对的总数。
样例
输入：[1,2,3,4,5,6,0]
输出：6

解法：归并排序

归并排序中，假设左右两边分别有序，然后左右两边依次比较，有序存入缓冲区，最后再复制回原数组
可以利用比较的过程计算逆序对的数目
如果左侧某个数i大于右侧某个数j，那么i后面的数自然也大于j
时间复杂度O(nlogn)，空间复杂度O(n)

  1. class Solution {
  2. public:
  3.     int merge_sort(vector<int> &nums, int l, int r) {
  4.         if (l >= r) return 0;
  6.         int res = 0;
  7.         int mid = l + r >> 1;
  8.         res += merge_sort(nums, l, mid);
  9.         res += merge_sort(nums, mid + 1, r);
  11.         vector<int> tmp;
  12.         int i = l, j = mid + 1;
  13.         while (i <= mid && j <= r) {
  14.             if (nums[i] > nums[j]) {
  15.                 res += mid - i + 1;
  16.                 tmp.push_back(nums[j++]);            
  17.             }
  18.             else tmp.push_back(nums[i++]);
  19.         }
  21.         while (i <= mid) tmp.push_back(nums[i++]);
  22.         while (j <= r) tmp.push_back(nums[j++]);
  24.         for (int i = l, j = 0; i <= r; i++, j++)
  25.             nums[i] = tmp[j];
  27.         return res;
  28.     }
  30.     int inversePairs(vector<int>& nums) {
  31.         return merge_sort(nums, 0, nums.size() - 1);
  32.     }
  33. };