【C++算法】48.分治_归并_数组中的逆序对

题目链接：

剑指 Offer 51. 数组中的逆序对

题目描述：

解法

解法一：暴力解法：暴力枚举

两层for循环

本题不能用，用了会超时。

解法二：

归并排序

C++ 算法代码：

class Solution 
{
    int tmp[50010]; // 用于在归并过程中临时存储排序后的元素
    public:
    int reversePairs(vector<int>& nums) 
    {
        return mergeSort(nums, 0, nums.size() - 1); //返回逆序对的数量
    }
    int mergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right) return 0; // 基本情况：区间内只有一个元素或为空，没有逆序对
        int ret = 0; // 用于存储当前区间内的逆序对数量
        // 1. 找中间点，将数组分成两部分
        int mid = (left + right) >> 1; // 使用位运算 (left + right) / 2 提高效率
        // [left, mid][mid + 1, right]
        // 2. 递归地对左右两个子区间进行排序，并计算逆序对数量
        // 左边的个数 + 排序 + 右边的个数 + 排序 
        v // 右半部分的逆序对
        // 3. 计算跨越左右两个子区间的逆序对数量
        // cur1指向第一个子数组的当前元素
        // cur2指向第二个子数组的当前元素
        // i指向临时数组的当前位置
        int cur1 = left, cur2 = mid + 1, i = 0;
        // 当两个子数组都还有元素时，比较并处理
        while(cur1 <= mid && cur2 <= right) // 升序的时候
        {
            if(nums[cur1] <= nums[cur2])
            {
                tmp[i++] = nums[cur1++];
            }
            else
            {
                // 当 nums[cur1] > nums[cur2] 时，说明 cur1 到 mid 之间的所有元素都大于 nums[cur2]
                // 因此，逆序对的数量为 mid - cur1 + 1
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }
        // 4. 处理一下排序
        while(cur1 <= mid) tmp[i++] = nums[cur1++];
        while(cur2 <= right) tmp[i++] = nums[cur2++];
        // 5. 将临时数组中的合并结果复制回原数组的对应位置
        for(int j = left; j <= right; j++)
            nums[j] = tmp[j - left];

        return ret; // 返回当前区间内的逆序对总数
    }
};

图解

例如：nums = [9, 7, 5, 4, 6]

1. mergeSort(nums, 0, nums.size() - 1);->mergeSort(nums, 0, 4);

   ret = 0;mid = 2;

   ret += mergeSort(nums, left, mid);->ret += mergeSort(nums, 0, 2);

2. mergeSort(nums, 0, 2);

   ret = 0;mid = 1;

   ret += mergeSort(nums, left, mid);->ret += mergeSort(nums, 0, 1);

3. mergeSort(nums, 0, 1);

   ret = 0;mid = 0;

   ret += mergeSort(nums, left, mid);->ret += mergeSort(nums, 0, 0);

4. mergeSort(nums, 0, 0);

   left = right -> return 0;

5. ret = 0;

   ret += mergeSort(nums, mid + 1, right);->ret += mergeSort(nums, 1, 1);

6. mergeSort(nums, 1, 1);

   left = right -> return 0;

7. mergeSort(nums, 0, 1);

   ret = 0;mid = 0;

   cur1=0;cur2=1;i=0

   进入while循环

   ret += mid - cur1 + 1;->ret += 0- 0+ 1=1
tmp[i++] = nums[cur2++];->tmp[0] = nums[1];->tmp[0]=7

   i=1;cur2=2，跳出while循环

   cur1<mid，tmp[i++] = nums[cur1++];->tmp[1] = nums[0];->tmp[1]=9

   i=2;cur1=1

   进入for循环

   nums[0]=7

   nums[1]=9

   return 1

   

8. mergeSort(nums, 0, 2);

   ret = 1;mid = 1;

   ret += mergeSort(nums, mid + 1, right);->ret += mergeSort(nums, 2, 2);

   

9. mergeSort(nums, 2, 2);

   left = right -> return 0;

   

10. mergeSort(nums, 0, 2);

    ret = 1;mid = 1;

    cur1=0;cur2=2;i=0

    进入while循环

    ret += mid - cur1 + 1;->ret = ret + 1- 0+ 1=3
tmp[i++] = nums[cur2++];->tmp[0] = nums[2];->tmp[0]=5

    i=1;cur2=3，跳出while循环

    cur1<=mid，tmp[i++] = nums[cur1++];->tmp[1] = nums[0];->tmp[1]=7

    i=2;cur1=1

    cur1<=mid，tmp[i++] = nums[cur1++];->tmp[2] = nums[1];->tmp[2]=9

    i=3;cur1=2

    进入for循环

    nums[0]=5

    nums[1]=7

    nums[2]=9

    return 3

    

11. mergeSort(nums, 0, 4);

    ret = 3;mid = 2;

    ret += mergeSort(nums, mid + 1, right); ->ret += mergeSort(nums, 3, 4);

    

12. mergeSort(nums, 3, 4);

    ret = 3;mid = 3;

    ret += mergeSort(nums, left, mid);->ret += mergeSort(nums, 3, 3);

    

13. mergeSort(nums, 3, 3);

    left = right -> return 0;

    

14. mergeSort(nums, 3, 4);

    ret = 3;mid = 3;

    ret += mergeSort(nums, mid + 1, right);->ret += mergeSort(nums, 4, 4);

    

15. mergeSort(nums, 4, 4);

    left = right -> return 0;

    

16. mergeSort(nums, 3, 4);

    ret = 3;mid = 3;

    cur1=3;cur2=4;i=0

    进入while循环

    tmp[i++] = nums[cur1++];->tmp[0] = nums[3];->tmp[0] = 4

    i=1;cur1=4，跳出while循环

    cur2<=right;tmp[i++] = nums[cur2++];->tmp[1] = nums[4];->tmp[1] = 6

    i=2;cur2=5

    进入for循环

    nums[3]=4

    nums[4]=6

    return 3

    

17. mergeSort(nums, 0, 4);

    ret = 3;mid = 2;

    cur1=0;cur2=3;i=0

    进入while循环

    ret += mid - cur1 + 1;->ret = ret + 2- 0+ 1= 3 +3 =6
tmp[i++] = nums[cur2++];->tmp[0] = nums[3];->tmp[0]=4

    i=1;cur2=4

    nums[cur1]<=nums[cur2];->tmp[i++] = nums[cur1++];->tmp[1] = nums[0];->tmp[1]=5

    i=2;cur1=1

    ret += mid - cur1 + 1;->ret = ret + 2- 1+ 1= 6 +2 =8
tmp[i++] = nums[cur2++];->tmp[2] = nums[4];->tmp[2]=6

    i=3;cur2=5

    跳出while循环

    cur1=1,cur2=5

    cur1<=mid，tmp[i++] = nums[cur1++];->tmp[3] = nums[1];->tmp[3]=7

    i=4;cur1=2

    cur1<=mid，tmp[i++] = nums[cur1++];->tmp[2] = nums[2];->tmp[4]=9

    i=5;cur1=3

    进入for循环

    nums[0]=4

    nums[1]=5

    nums[2]=6

    nums[3]=7

    nusm[4]=9