leetcode----归并排序

剑指 Offer 51. 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:
输入: [7,5,6,4]
输出: 5

思路：采用归并排序算法(n*log(n))，边排序边更新逆序对；归并排序算法中用到了分治+递归的思想；
核心代码块为：key0、key1、key2、key3

class Solution {
public:
    int SortAndGetCount(vector<int>& nums, int left, int mid, int right)
    {
        if (left == right) { // key0，终止条件
            return 0;
        }
        int leftCount = SortAndGetCount(nums, left, (left + mid) / 2, mid); // key1，递归
        int rightCount = SortAndGetCount(nums, mid + 1, (mid + 1 + right) / 2, right); // key1，递归
        for (int i = left; i <= right; i++) {
            tmp[i] = nums[i]; // key2, 对排完序的左右部分做临时缓存
        }
        int i = left; // key3
        int j = mid + 1; // key3
        int count = 0;
        for (int k = left; k <= right; k++) { // key3，核心中的核心，进行合并
            if (i == mid + 1) { // key3, 左边已空
                nums[k] = tmp[j];
                j++;
            } else if (j == right + 1) { // key3, 右边已空
                nums[k] = tmp[i];
                i++;
            } else if (tmp[i] <= tmp[j]) { // key3
                nums[k] = tmp[i];
                i++;
            } else { // key3
                nums[k] = tmp[j];
                j++;
                count += (mid - i + 1); // key4, 逆序对个数为前面的的数组在当前遍历的数之后剩余的数量
            }
        }
        return (leftCount + rightCount + count); // key5
    }

    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return 0;
        }
        tmp = vector<int>(n);
        int left = 0;
        int right = n - 1;
        int mid = left + (right - left) / 2;
        return SortAndGetCount(nums, left, mid, right);
    }

private:
    vector<int> tmp;
};

315. 计算右侧小于当前元素的个数
     给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例：
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

提示：
0 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

思路：采用归并排序，对于排好序的左右两部分，只需更新左边的下标，记录右边有多少数字比当前数字小即可，采用累加贡献数量curCount进行记录 ；

class Solution {
public:
	void SortAndCount(vector<vector<int>>& data, int left, int mid, int right)
	{
		if (left == right) {// key0，终止条件
			return;
		}
		SortAndCount(data, left, (left + mid) / 2, mid); // key1，递归
		SortAndCount(data, mid + 1, (mid + 1 + right) / 2, right); // key1，递归
		for (int i = left; i <= right; i++) {
			tmp[i] = data[i]; // key2, 对排完序的左右部分做临时缓存
		}
		int curCount = 0; // 记录累加贡献值
		int i = left; // 指向左边，key3
		int j = mid + 1; // 指向右边，key3
		for (int k = left; k <= right; k++) {// key3
			if (i == mid + 1) {
				data[k] = tmp[j];
				j++;
			} else if (j == right + 1) {
				data[k] = tmp[i];
				out[tmp[i][0]] += curCount;
				i++;
			} else if (tmp[i][1] <= tmp[j][1]) { // key3
				data[k] = tmp[i];
				out[tmp[i][0]] += curCount;
				i++;
			} else if (tmp[i][1] > tmp[j][1]) { // key3
				data[k] = tmp[j];
                curCount += 1;
				j++;
			}
		}
	}

	vector<int> countSmaller(vector<int>& nums) {
		int n = nums.size();
		if (n == 0) {
			return {};
		}
		out = vector<int>(n, 0);
		tmp = vector<vector<int>>(n, vector<int>(2, 0)); // 用于归并排序的临时空间
		vector<vector<int>> data(n, vector<int>(2, 0)); // 记录序号和值
		for (int i = 0; i < n; i++) {
			data[i][0] = i;
			data[i][1] = nums[i];
		}
		SortAndCount(data, 0, (n - 1) / 2, n - 1);
		return out;
	}

private:
	vector<int> out;
	vector<vector<int>> tmp;
};