本文共 1389 字，大约阅读时间需要 4 分钟。

题目

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

思路

直接上了个力扣的代码，自己写了较详细的注释。

题解：

基本思路就是归并的基础上加上计数

视频从6:30开始看就行了

代码

class Solution {public:int mergeSort(vector
   
    & nums, vector
    
     & tmp, int l, int r) {        //递归结束条件，一个数当然是有序的        if (l >= r) {            return 0;        }        //找中间值        int mid = (l + r) / 2;        //递归：计算左边的和右边的两个部分的逆序数        int inv_count = mergeSort(nums, tmp, l, mid) + mergeSort(nums, tmp, mid + 1, r);                int i = l, j = mid + 1, pos = l;                while (i <= mid && j <= r) {            if (nums[i] <= nums[j]) {                tmp[pos] = nums[i];                ++i;                //只在左边比右边小的时候计数                inv_count += (j - (mid + 1));            }            else {                tmp[pos] = nums[j];                ++j;            }            ++pos;        }        //这个过程就是把剩下来没弄进原数组的弄回去        for (int k = i; k <= mid; ++k) {            tmp[pos++] = nums[k];            //只在加左边的时候计数            inv_count += (j - (mid + 1));        }        for (int k = j; k <= r; ++k) {            tmp[pos++] = nums[k];        }        //内存拷贝一次        copy(tmp.begin() + l, tmp.begin() + r + 1, nums.begin() + l);        return inv_count;    }    int reversePairs(vector
     
      & nums) {        int n = nums.size();        vector
      
        tmp(n);        return mergeSort(nums, tmp, 0, n - 1);    }};
      
     
    
   

转载地址：https://blog.csdn.net/hanmin822/article/details/105957563 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！