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

#include <vector>
#include <string>
#include <iostream>

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型
     */
    vector<int> temp;
    int InversePairs(vector<int>& nums) {
        // write code here
        temp = vector<int>(nums.size());
        return this->merge_sort(nums, 0, nums.size() - 1);
    }

    // 递归 归并排序
    int merge_sort(vector<int>& vec, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = (right + left) >> 1;
        //cout << "left:" << left << ", mid:" << mid << ", right:" << right;
        //cout << ", left nums:" << this->print_vec(vec, left, mid);
        //cout << ", right nums:" << this->print_vec(vec, mid + 1, right) << endl;
        int inverse_cnt = this->merge_sort(vec, left, mid) + this->merge_sort(vec,
                          mid + 1, right);
        int l = left, cursor = left, r = mid + 1;

        // 左右数组选取数字升序排序 左数组或右数组超限时 停止
        while (l <= mid && r <= right) {
            // 当左数组的l++首先超出限制时 说明左数组的所有值都小于右数组 r 处对应的值 temp中存放的是已排好序的值
            if (vec[l] <= vec[r]) temp[cursor++] = vec[l++];
            else {  // 当右数组的r++首先超出限制时 说明右数组的所有值都小于左数组 l 处对应的值
                temp[cursor++] = vec[r++];
                // 仅对归并排序添加一行代码即可完成逆序数对的统计
                // 右侧小于左侧时 产生逆序数对 左数组(已升序)中 l~mid 处的数值均大于右数组r处当前值
                inverse_cnt += mid - l + 1;
                inverse_cnt %= (int)(1e9+7);
            }
        }

        // 当l或r超限时 剩下的数据(不一定有序)copy进入temp中 待外层递归时 while进行排序
        // 先将左数组剩余(说明右数组已全部进入temp数组)的数据 均大于temp中的最大值 copy进入temp中
        for (; l <= mid; l++) temp[cursor++] = vec[l];
        // 将右数组剩余(说明左数组已全部进入temp数组)的数据 均大于temp中的最大值 copy进入temp中
        for (; r <= right; r++) temp[cursor++] = vec[r];

        // 对应位置局部已排好序 复制给原数组
        for (; left <= right; left++) vec[left] = temp[left];
        //cout << "after part sort:" << this->print_vec(vec) << endl;
        //cout << "part sort finish" << endl;
        return inverse_cnt;
    }

    string print_vec(vector<int>& vec) {
        string str = "";
        for (auto num : vec) {
            str.append(to_string(num));
            str.append(",");
        }
        string result = str.substr(0, str.length() - 1);
        return "[" + result + "]";
    }

    string print_vec(vector<int>& vec, int start_idx, int end_idx) {
        string str = "";
        for (; start_idx <= end_idx; start_idx++) {
            str.append(to_string(vec[start_idx]));
            str.append(",");
        }
        string result = str.substr(0, str.length() - 1);
        return "[" + result + "]";
    }
};