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

不得不说对归并的使用很巧妙

也利用两个有序无序数组，其逆序对数一样以及对于有序递增序列，其某个数字的逆序对可以一次求出的性质

class Solution {
  public:
    int InversePairs(vector<int> data) {
        //  边界判断
      if (data.empty() || data.size() == 1) {
        return 0;
      }
      
        //  归并算法的辅助空间和计数器
      std::vector<int> tmp(data.size());
      int count = 0;
      
        //  归并
      div(data, tmp, 0, data.size() - 1, count);
      
      return count;
    }
  private:
    void div(std::vector<int> &data, std::vector<int> &tmp, int left, int right, int &count) {
      // 归并时最少有两个子数组进行组合排序，等于时就需要终止
      if (left >= right) {
        return ;
      }
      
      int mid = left + ((right - left) >> 1);  // 移位操作比除法更快
      div(data, tmp, left, mid, count);
      div(data, tmp, mid + 1, right, count);
      merge(data, tmp, left, mid, right, count);
    }
    
    void merge(std::vector<int> &data, std::vector<int> &tmp, int left, int mid, int right, int &count) {
        //  两个子数组的起始索引和辅助空间的索引
      int fir_arr = left, sec_arr = mid + 1, tmp_index = 0;
      
      while (fir_arr <= mid && sec_arr <= right) {
          //  成立则构成逆序，而该子数组又是有序递增数组，可求总的逆序对
          //  和常规归并排序的差别在于逆序时统计逆序对
        if (data[fir_arr] > data[sec_arr]) {
          tmp[tmp_index++] = data[sec_arr++];
          count += (mid - fir_arr + 1);
          count %= mod;
        } else {
          tmp[tmp_index++] = data[fir_arr++];
        }
      }
      
        //  两个while遍历某一个未遍历完的数组
      while (fir_arr <= mid) {
        tmp[tmp_index++] = data[fir_arr++];
      }
      
      while (sec_arr <= right) {
        tmp[tmp_index++] = data[sec_arr++];
      }
      
        //  拷贝回原数组
      for (tmp_index = 0, fir_arr = left; fir_arr <= right; ++fir_arr, ++tmp_index) {
        data[fir_arr] = tmp[tmp_index];
      }
    }
  private:
    const int mod = 1'000'000'007;
};