题解 | #数组中的逆序对#

#include <vector>

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
	 * 这是二路归并排序的算法题，重点是需要一个辅助的数组，将原来的数据存放到辅助的数组
	 一旦存放到辅助数组上，再下一轮的合并中，原始数据的位置就会成为目的地址，或者将上一轮的两个有序
	 子序列的内容，先放到原始数组中，合并时再放到dst数组中，这样保存了dst的属性在整个算法的含义一致性，
	 但也由此消耗了一些性能；
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int InversePairs(vector<int>& nums) {
      if (nums.empty() || nums.size() == 1)
        return 0;

      std::vector<int> dst(nums.size(), -1);
      return InversePairs(nums, dst, 0, nums.size()-1);
    }

    int InversePairs(vector<int>& nums, vector<int>& dst, int left, int right) {
      if (left >= right) {
        dst[left] = nums[left];
        return 0;
      }
  
      auto mid = left + ((right - left) >> 1);
      auto ret = InversePairs(nums, dst, left, mid) + InversePairs(nums, dst, mid+1, right);
      ret %= mod_;
      // InversePairs返回的结果放在dst中，而nums中的数据已不需要了。
      // 这个时候，为了保证合并之后的正确的序列仍然放在dst中，可以将nums和dst子left和right之间的数据进行交换；
      for (int i = left; i <= right; ++i) {
        nums[i] = dst[i];  
      }

      auto i = mid, j = right;
      auto k = right;
      auto count = 0;
      while (i >= left && j >= mid+1) {
        if (nums[i] > nums[j]) {
          count += j - mid; // 累加逆序对个数
          dst[k--] = nums[i--]; // 排序，将当前最大放入到dst中
        } else {
          dst[k--] = nums[j--]; // 排序，将当前最大放入到dst中
        }
      }

      while (i >= left)  // 如果右边的数组已无数据，就需要将左边的数据放入dst数组中
        dst[k--] = nums[i--];
      
      while (j >= mid+1)// 如果左边的数组已无数据，就需要将右边的数据放入到dst数组中
        dst[k--] = nums[j--];
      
      return (ret + count) % mod_;
    }

  private:
   int mod_ {1000000007};
};