题解 | #计算数组的小和#

利用归并排序可以记录比较大小的过程，且无重复不遗漏的特点，来计算小和。

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return long长整型 */

long long process (vector &nums, int l, int r) { //归并框架 if (l == r) { return 0;//一个数是有序的 } int mid = l + ((r - l) >> 1); return process(nums,l, mid) +process(nums, mid + 1, r) + merge(nums, l, mid, r); //左半区小和 + 右半区小和 + 左右merge产生的小和 }

long long merge (vector<int> &nums, int l, int mid, int r) {//merge过程中进行小和的计算统计
    vector<int> temp(r - l + 1);
    long long sum = 0;
    int p1 = l;
    int p2 = mid + 1;
    int k = 0;
    while (p1 <= mid && p2 <= r) {
        //sum += nums[p1] <= nums[p2] ? (r - p2 + 1) * nums[p1] : 0;
        //temp[k++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
        if (nums[p1] <= nums[p2]) {    //p1<=p2,p1存入零时空间，并产生小和
            sum += (r - p2 + 1) * nums[p1]; //p1<=p2,左右两侧都是有序递增的，则p1小于p2及p2右侧所有的数，为（r-p2+1）个数的小和
            temp[k++] =  nums[p1++];
        }
        else {
            temp[k++] =  nums[p2];
            p2++;
        }
    }
    while(p1 <= mid) {//右侧已经溢出，右侧无数，没有小和
        temp[k++] = nums[p1++];
    }
    while (p2 <= r) {//只有左侧的数才能产生小和，左侧已经溢出，故没有小和
        temp[k++] = nums[p2++];
    }
    for (int j= 0; j < r-l+1; j++) { //写回原数组，使得l-r区域有序，参与到下一次merge中。
        nums[j + l] = temp[j];
    }
    return sum;
}


long long calArray(vector<int>& nums) {
    return process(nums,0,nums.size()-1);
}

};