归并分治问题练习和题解

文章目录

• 简介
• 排序数组
• • 原理
  • 代码
  • 交易逆序对的总数
  • • 原理
    • 代码跑的过程
    • 代码
    • 计算右侧小于当前元素的个数
    • • 原理
      • 代码
      • 翻转对
      • • 代���

          简介

          大家好,这里是jiantaoyab,这篇文章给大家带来的是归并类型相关的题目练习和解析,涉及到递归的题目大家可以画递归展开图来方便理解,后面的题目有点绕,大家耐心想想就能理解,希望大家能相互讨论进步

          排序数组

          https://leetcode.cn/problems/sort-an-array/

          原理

          递归展开图

          代码

          class Solution {    vector tmp; //辅助数组public:    //归并排序    void MergeSort(vector& nums, int l, int r)    {        if(l >= r) return;        int mid = (r + l) >> 1; //中间点        //左右区间排序        MergeSort(nums, l, mid);        MergeSort(nums, mid+1, r);        int cur1 = l, cur2 = mid + 1, i = 0;        //合并2个有序数组        while(cur1