详解一道字节跳动的二面题目，它太经典了！

水深无声 2023-03-04 09:11 109阅读 0赞

点击上方“**图解面试算法**”，选择“星标”公众号

重磅干货，第一时间送达![format_png][]

![format_png 1][]

大家好，我是程序员景禹，今天给大家分享一道力扣题目：

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

这个问题在各个大厂的面试中经常出现，因为它真的太经典，太完美！

## 题目描述 ##

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

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

逆序对的数目可以标识一个数组和有序数组之间的距离，逆序对的数目越少，数组变成有序数组的步数就越少；逆序对越多，原数组变成有序数组就需要更多的步骤。

对于一个有序的数组而言，逆序对的数目就是 0，而一个完全逆序的数组，逆序对的数目当然也就最多！

举个例子(前提假设升序为有序)，数组\[1，2，3\]，逆序对的数目为零；而数组\[3，2，1\]的逆序对就是3，分别为(3，2)、(3，1)和(2，1)。

举一个很具普适性的例子，对于一个包含 n 个数且无重复的逆序数组，逆序对的数目就等于 (n-1)+(n-2)+……+3+2+1=n(n-1)/2。

### 示例 ###

输入: arr[]={8，5，4，2，1}
    输出: 10
    解释: 逆序对为(8，5)、(8，4)、(8，2)、(8，1)，(5，4)、(5，2)、(5，1)，还有(4，2)、(4，1)和(2，1)，总共10个。其实也可以直接计算5(5-1)/2=10，前提是知道数组完全逆序
    
    输入: arr[]={5，1，4，2，8}
    输出: 4
    解释: 逆序对为(5，1)、(5，4)、(5，2)，还有(4，2)，总共4个。
    在这里也可以看出数组{5，1，4，2，8}比{8，5，4，2，1}更有序，逆序对的数目可以衡量一个数组的有序程度。

## 题目解析 ##

### 蛮力法 ###

两层for循环就可以解决了，这里就不过多介绍，提供的代码仅供参考。

但是这种方式，存在很多不必要的运算，举个简单的例子，比如对数组 `[2,1,3,4,5,6]` 而言，仅包含一个逆序对 `(2,1)` ，正常情况下，我们仅需要比较一次，而蛮力法需要比较 5(5 + 1)/2 = 15 次。

也就是说，与我们期望的比较次数，蛮力法存在 14 次不必要的比较操作，后面要讲的其他方法事实上就是努力将这种不必要的次数降到最低。

#### 实现代码 ####

class Solution {
        public int reversePairs(int[] nums) {
            int count = 0;
            int n = nums.length;
            for(int i = 0;i < n - 1; i++){
                for(int j = i+1; j < n; j++){
                    if(nums[i] > nums[j]){
                        count++;
                    }
                }
            }
            return count;
        }
    }

#### 复杂度分析 ####

*  时间复杂度：
 *  空间复杂度：

### 归并排序 ###

在正式讲解归并排序如何统计逆序对的数目之前，建议您先看一下 [图解「归并排序」算法（修订版）][Link 1] ，熟悉了归并排序，再看题解就会很清晰！

关于归并排序的好多问题，一般都是从合并的角度进行考虑，统计逆序对同样如此。

我们以数组 **`[8，5，4，2，1]`** 为例进行具体讲解。

关于归并排序分的过程，就不在这里详细，大家直接看下图：

![format_png 2][]

我们直接看合并过程中是如何统计逆序对的数目的，初始化逆序对的数目 **`count = 0`** .

第一步，合并 **8** 和 **5** ，**8 > 5** ，为一个逆序对，**`count = count + 1 = 1`**![format_png 3][]

第二步，合并 **`[5,8]`** 和 **4** ，**5 > 4** ，因为 **`[5,8]`** 已经有序，所以 **5** 之后的元素都比 **4** 大，所以直接合并，而 **`count`** 的数目加 **`(mid+1) - (l + i) = 2`** ，即逆序对就等于 **`count = 3`** 。说明，合并两个有序的数组，当第一个数组的指针 **`i`** 所指向的元素 大于后一个数组下标 **`j`** 所指向的元素，那么指针 **`i`** 所指向的元素及第一个数组中 **`i`** 之后的所有元素都应该大于第二个数组下标 **`j`** 所指向的元素，所以逆序对的数目应该加上 **mid - i + 1** ，而我们给加上了 **`(mid+1) - (l + i)`** 是为了保证边界的准确性。

![format_png 4][]

第三步，合并 **2** 和 **1** ，**2 > 1** ，是一个逆序对，所以 **`count`** 进行加一，即：**`count = 4`**

![format_png 5][]

第四步，合并数组 **`[4,5,8]`** 和数组 **`[1,2]`** .

**4** 和 **1** 比较，**4 > 1** ，所以 **`[4,5,8]`** 肯定均大于 **1** ，逆序对的数目就加上 **`3 = (mid+1) - (l + i)`** , **`count = 7`** 。

![format_png 6][]

然后 **`j`** 向右移动，即，**`j++`** ；**4** 和 **2** 比较，**4 > 2** ，所以 **`[4,5,8]`** 肯定均大于 **1** ，逆序对的数目就加上 **`3 = (mid+1) - (l + i)`** ，**`count = 10`** .

![format_png 7][]

**`j`** 再向右移动，则会大于 **`r`** ，合并结束，逆序对的数目就是 **count = 10** ，返回即可。

#### 实现代码 ####

class Solution {
        //合并函数
        private static int mergeAndCount(int[] arr, int l, int m, int r) 
        { 
            int[] left = Arrays.copyOfRange(arr, l, m + 1); 
    
            int[] right = Arrays.copyOfRange(arr, m + 1, r + 1); 
      
            int i = 0, j = 0, k = l, swaps = 0; 
      
            while (i < left.length && j < right.length) { 
                if (left[i] <= right[j]) 
                    arr[k++] = left[i++]; 
                else { 
                    arr[k++] = right[j++]; 
                    swaps += (m + 1) - (l + i); 
                } 
            } 
    
            while (i < left.length) 
                arr[k++] = left[i++]; 
     
            while (j < right.length) 
                arr[k++] = right[j++]; 
      
            return swaps; 
        } 
      
        // 归并排序
        private static int mergeSortAndCount(int[] arr, int l, int r) 
        { 
            int count = 0; 
      
            if (l < r) { 
                int m = (l + r) / 2; 
      
                count += mergeSortAndCount(arr, l, m); 
    
                count += mergeSortAndCount(arr, m + 1, r); 
    
                count += mergeAndCount(arr, l, m, r); 
            } 
      
            return count; 
        }     
        public int reversePairs(int[] nums) {
            return mergeSortAndCount(nums, 0, nums.length-1);
        }
    }

#### 复杂度分析 ####

*  时间复杂度：，归并排序的时间复杂度，在 [图解「归并排序」算法（修订版）][Link 1] 里面有严格证明。
 *  空间复杂度：，合并过程使用了额外的空间。

### 树状数组 ###

树状数组既是树，又是数组，关于树状数组的详细介绍，强烈推荐你看一下 [漫画：什么是树状数组？][Link 2] 这篇文章。

之前写树状数组的文章时，我强调过树状数组的核心思想并不在 **`BITree[]`** 树状数组，而在于对下标的巧妙利用。

而要利用树状数组统计一个数组当中逆序对的数目，我们同样要充分利用下标的特性进行。

对于数组 **`[8,5,4,2,1]`** 而言，首先我们找出数组当中的最大值 **8** ，这一个步骤时间复杂度为.

然后以这个最大值 **8** 为最大下标，建立一个树状数组 **`BITree[]`** ，并初始化为 **0** 。

接下来从后向前扫描 **`arr[]`** 数组，边统计逆序对，边往树状数组 **`BITree[]`** 里面添加元素。

第一步：下标 **`i = n - 1 = 4`** ，**`arr[4] = 1`** ，调用 **`getSum()`** 函数计算逆序对，然后调用 **`updateBIT()`** 函数往 **`BITree[]`** 里面添加元素，具体我们分步骤介绍一下。

1.  调用 **`getSum()`** 函数计算逆序对。

**`getSum()`** 函数与之前专门讲树状数组中实现并无差别，只不过我们传入的索引数 **`index`** 比较特殊， **`index = arr[i] - 1`** .

static int getSum(int[] BITree, int index) 
    { 
        int sum = 0; 
        while (index > 0) 
        { 
            //将当前 BITree[] 的值加到 sum 中
            sum += BITree[index]; 
            //找到 index 的父结点
            index -= index & (-index); 
        } 
        return sum; 
    }

因此事实上我们调用的就是 **`getSum(BITree, arr[i] - 1)`** ，即 **`getSum(BITree, 0)`** ，因为 **`arr[4] - 1 = 0`** ，所以函数返回 **0** ，即当前元素 **arr\[4\]** 之后不存在逆序对。

**提示：对 `getSum()` 函数执行过程不清楚的可以看下图，之后所有的 `getSum()` 调用都直接给出结果。**

![format_png 8][]

此处你可能有些懵逼，不急，接着看。

1.  调用 **`updateBIT()`** 函数往 **`BITree[]`** 里面添加元素

更新树状数组的函数：

static void updateBIT(int[] BITree, int n, int index, int val) 
    { 
        while (index <= n) 
        { 
            BITree[index] += val; 
            index += index & (-index); 
        } 
    }

在更新树状数组时，**`updateBIT(BIT, maxElement, arr[i], 1);`** ，即 **`updateBIT(BIT, 8, 1, 1);`** 更新完之后树状数组如下所示：

![format_png 9][]

具体为什么更新位置 **1、2，4，8** ，大家还是看树状数组的文章。到这里，逆序对的数目还是零，我们根本感受不到树状数组的妙用，它是如何统计逆序对的数目的？不急，接着看。

第二步：下标 **`i = 3`** ，**`arr[3] = 2`**

调用 **`getSum(BITree, 1)`** ， **`sum += BITree[1] = 1`** 统计出逆序一个逆序对 **（2，1）** ，逆序对的数目 **count = 1** .

在更新树状数组，即 **`updateBIT(BIT, 8, 2, 1);`** 更新完之后树状数组如下所示：![format_png 10][]

第三步：下标 **`i = 2`** ，**`arr[2] = 4`**

调用 **`getSum(BITree, 3)`** ，\*\*`sum = 2` \*\* ，统计出了逆序对 **（4，2）和 （4，1）** ，逆序对的数目等于 **count = 3**， 对函数 **`getSum()`** 执行过程不清楚的可以对照下图自行走一趟：

更新树状数组，即 **`updateBIT(BIT, 8, 4, 1);`** 更新完之后树状数组如下所示：![format_png 11][]

第四步：下标 **`i = 1`** ，**`arr[1] = 5`**

调用 **`getSum(BITree, 4)`** ，\*\*`sum = 3` \*\* ，统计出了逆序对 **（5，4）和 （5，2）、（5，1）** ，逆序对的数目等于 **count = 6** 。

更新树状数组，即 **`updateBIT(BIT, 8, 5, 1);`** 更新完之后树状数组如下所示：

![format_png 12][]

第五步：下标 **`i = 0`** ，**`arr[0] = 8`**

调用 **`getSum(BITree, 7)`** ，\*\*`sum = 4` \*\* ，统计出了逆序 **（8，5）、（8，4）、（8，2）、（8，1）** 。逆序对的数目等于 **count = 10** 。

更新树状数组，即 **`updateBIT(BIT, 8, 8, 1);`** 更新完之后树状数组如下所示：

![format_png 13][]

这样，我们就统计出了数组 **`[8,5,4,2,1]`** 中逆序对的数目。

但你一定困惑为什么树状数组可以统计出逆序对的数目，还有 **`BITree[]`** 树状数组中的元素的含义是什么？

第一个问题：树状数组之所以能够统计出逆序对的数目，是因为树状数组事实上将原始数组 **arr\[\]** 映射到了一个有序的下标上，这句话该如何理解呢，且看下图：

![format_png 14][]

而将数组 **arr\[\]** 中的元素作为树状数组 **`BITree[]`** 的下标，表示的意义就是当前元素 **arr\[i\]** 的右侧比 **arr\[i\]** 小的元素的数目，这个数目也就是逆序对的数目。

事实上，按照树状数组 **`BITree[]`** 本身的意义， **`BITree[i]`** 应该表示原始数组 **`arr[]`** 中前 **`i`** 个元素的累加和，而我们这里隐含的缺少了这个原始数组，这个原始数组应该是一个全为 **1** 的数组。

![format_png 15][]

我想你现在应该清晰啦！

第二个问题：**`BITree[index]`** 树状数组中的元素的含义是：在 **`updateBIT()`** 执行更新前， **`BITree[index]`** 表示原始数组 **`arr[]`** 中元素 **index = arr\[i\]** 的右侧比 **index** 小的元素的数目。

这个代码事实上很好写，前提是你真的明白树状数组，当然你不明白也没事啦，因为树状数组不是我们面试必须掌握的内容，所以可以直接跳过了！我用你必须会的知识点（比如上面的方法二提到的归并排序），带你再来解决这个问题一次。

总结一下，利用树状数组 **`BITree[]`** 统计数组 **`arr[]`** 中逆序对的步骤。

1.  创建一个树状数组 **`BITree[maxElement]`** ，其中 `maxElement` 表示数组 `arr[]` 中最大元素；
2.  从后向前遍历数组 **`arr[]`** :

*  对于数组中的每一个元素统计该元素右侧大于该元素的数字个数，使用 `getSum()` 函数计算。
 *  更新 **`BITree[]`** 树状数组（注意每次更新的 `val = 1` 是因为我们的树状数组此时表示的意义是，比 `index` 小且在数组 `arr[]` 中的元素数目；

代码写起来很简单。

#### 实现代码 ####

class Solution {
        private static int getSum(int[] BITree, int index) 
        { 
            int sum = 0;
            while(index > 0){
                sum += BITree[index];
                index -= index & (-index);
            }
    
            return sum;
        } 
     
        private static void updateBITree(int[] BITree, int n, 
                                         int index, int val) 
        { 
            while(index <= n){
                BITree[index] += val;
                index += index & (-index);
            }
        }     
        public int reversePairs(int[] nums) {
            int count = 0;
            int maxElement = 0;
            int n = nums.length;
            int[] arr = new int[n];
            for(int i = 0; i < n; i++){
                if(nums[i] > 0){
                    arr[i] = nums[i];
                }else{
                    arr[i] = -nums[i];
                }
            }
            for(int i = 0; i < n; i++){
                if(arr[i] > maxElement){
                    maxElement = arr[i];
                }
            }
    
            int[] BITree = new int[maxElement + 1];
            for(int i = 0; i < BITree.length; i++){
                BITree[i] = 0;
            }
            
            for(int i = n - 1; i >= 0; i--){
                count += getSum(BITree, arr[i] - 1);
                updateBITree(BITree, maxElement, arr[i], 1);
            }
    
            return count;
        }
    }

但是高兴太早了，上面的代码并没有通过 LeetCode 上的所有测试用例。提交一次，你就会发现，因为我们的代码没有考虑数组 **`arr[]`** 中存在负数的情况。

所以我就考虑将整个原始的数组 `arr[]` 映射到 1 和 n 之间。

这一次我们以数组 `arr[] = [2,-8,5,-4,1]` 为例，再来完整地走一遍树状数组的实现。这次让你看到树状数组当中的树。

##### 将原始数组 `arr[]` 映射到 1 到 n 之间，n 为数组长度？ #####

在介绍之前，我先给大家科普一个 C++ 的内置函数 `lower_bound()` ，用来求一个数组中第一个大于等于所要查找的元素的地址，具体的原理是二分查找，因此它只能用于**非降序序列**。

还有一个小问题，关于两个同类型的指针的减法运算：

int a[] = {1,2,3,4};
    int *temp = (int *)a;
    int *p = temp + 2;
    
    std::size_t s2 = p - temp;

同类指针（当然也只有同类指针允许相减，如 p 和 temp）相减得到的整数值，等于两指针减的距离除以 `sizeof(声明指针的类型)` ，即 `s2 = 8 / 4 = 2` 。

接下来我们就可以看一下将原始数组 `arr[]` 映射到 1 到 n 的过程了。

第一步：对于数组 `arr[]` 拷贝到临时数组 `temp[]` 当中，然后对临时数组 `temp[]` 进行排序，即 `temp[] = {-8,-4,1,2,5}` .

然后就是遍历数组 `arr[]` ，并将数组 `arr[]` 中的元素映射到 1 到 n 之间。

`arr[0] = 2` ，调用 `lower_bound(temp, temp + n， arr[0])` ，该函数返回 `arr[0]` 在数组 `temp[]` 当中的地址，也就是 `&temp[3]` ，然后用 `&temp[3] - temp` ，即两个地址之差，也就是 3，然后更新 `arr[0] = 3 + 1 = 4` .

同理 `arr[1]` 将被更新为 `arr[1] = 1` ;

以此类推，我们得到映射后的数组 `arr[] = {4,1,5,2,3}` .

为了避免你有这里都出现困惑，看下图：

![format_png 16][]

你就把我们上面解释的映射过程理解为，对原始数组 `arr[]` 排序后保存在临时数组 `temp[]` 当中，然后遍历原始的数组 `arr[]` 并进行映射操作，而这里的映射操作就是拿到数组 `arr[]` 中的一个元素 `arr[i]` （比如 `arr[0] = 2` ) ，然后在 `temp[]` 数组中找到 `arr[i]` 的位置（下标）`index` (就是图中红色的数字 3) ，然后将这个下标加一并赋值给 `arr[i]` (即 `arr[0] = 4` )。

接下来就是树状数组发挥作用的时候啦！![format_png 17][]

仔细观察，初始时 **`BITree[]`** 树状数组都为零，在树中也是零，而更新树状数组 **`BITree[]`** 按照下标 `3,2,5,1,4` 的顺序进行更新，更新的值 `val = 1` 。

更新之后的树状数组为：

![format_png 18][]

树状数组中的元素 `BITree[i] - 1` 就表示原始数组元素 `i` 的右侧比 `i` 小的元素个数。

举个栗子就好理解了，比如`BITree[4] - 1 = 3` ，就表示原始数组 `arr[]` 中元素 **4** 的右侧比 **4** 的元素的个数，即 **（4，1）、（4，2）和 （4，3）** 三个逆序对。

而整个数组当中的逆序对就等于 `(1-1) + (2-1) + (1-1) + (4-1) + (1-1) = 4` .

#### 实现代码 ####

class Solution {
    
        int getSum(int BITree[], int index){
            int sum = 0;
            while(index > 0){
                sum += BITree[index];
                index -= index & (-index);
            }
    
            return sum;
        }
        void updateBIT(int BITree[], int n, int index, int val){
            while(index <= n){
                BITree[index] += val;
                index += index & (-index);
            }
        }
    
        void convert(vector<int>& nums) 
        { 
            int n = nums.size();
            int temp[n];
            for(int i = 0; i < n; i++){
                temp[i] = nums[i];
            }
            sort(temp, temp + n);
    
            for(int i = 0; i < n; i++){
                nums[i] = lower_bound(temp, temp + n, nums[i]) - temp + 1;
            }
        } 
    
    public:
        int reversePairs(vector<int>& nums) {
            int count = 0;
            int n = nums.size();
            if(n <= 0){
                return count;
            }
            convert(nums);
            int BITree[n + 1];
            for(int i = 0; i <= n; i++){
                BITree[i] = 0;
            }
    
            for(int i = n - 1; i >= 0; i--){
                count += getSum(BITree, nums[i] - 1);
                updateBIT(BITree, n, nums[i], 1);
            }
    
            return count;
        }
    };

#### 复杂度分析 ####

*  时间复杂度：`updateBIT()` 和 `getSum()` 的时间复杂度均为，而更新树状数组的函数 `updateBIT()` 被运行了 n 次，整个算法的时间复杂度为.
 *  空间复杂度：，需要空间为 n 的树状数组 `BITree[]` .

如果树状数组的没有看懂，没有关系，这个不是必须掌握的内容！

### AVL平衡二叉树法 ###

事实上这可以算是一类方法，你可以选择二叉排序树 BST，但是 BST 对于一个有序数组可能存在单链的情况，你也可以选择红黑树，但红黑树可能比较复杂，所以我们可以选择介于两者之中的平衡二叉树来实现逆序对的统计。

对AVL 树存在疑惑的可以看看这篇文章：[图解：什么是AVL树？][AVL] 。

使用自平衡二叉排序树（如红黑树，AVL树等）并对其进行扩充，以便每个结点可以保存其右子树中的结点个数，即比结点本身大的结点个数。

创建一颗 AVL 树，这颗 AVL 树中的每一个结点包含它的子树中结点个数。

遍历数组 `arr[]` ,对每一个元素插入 AVL 树中

可以通过检查当前插入结点中右子结点的子树大小，来找到大于当前元素的结点数，从而可以确保当前节点的右子树中的元素的值均大于结点。

所以将插入结点中右子树中的大小数就是逆序对的数目，将所有结点插入之后得到的逆序数累计即可。

对于数组 `[8，5，4，2，1]` 而言.

插入关键字 **8** ，此时树为空，`count = 0` ，`8->size = 1`:

![format_png 19][]

插入关键字 **5** ，比根结点 **8** 小，`count = count + 8->size = 1` , `5->size = 1` :

![format_png 20][]

插入关键字 **4** ，比根结点 **8** 小，`count = count + 8->size = 2` ；与 **5** 比较，**4 < 5** ，`count = count + 5->size = 3` ；右旋，**5** 的 `size` 变成了 **2** ，即 **`5->size = 2`** :

![format_png 21][]

插入关键字 **2** ，比根结点 **5** 小， `count = count + 5->size = 5` ；与 **4** 比较，**2 < 4** ，`count = count + 4->size = 6` :

![format_png 22][]

插入关键字 **1** ，比根结点 **5** 小， `count = count + 5->size = 8` ；与 **4** 比较，**1 < 4** ，`count = count + 4->size = 9` ；与 **2** 比较，**1 < 2** ，`count = count + 2->size = 10` 。

![format_png 23][]

#### 实现代码： ####

class Solution {
        // AVL 树的结点
        struct Node 
        { 
            int key, height; 
            struct Node *left, *right; 
            //以 this.Node 为根的树的大小
            int size;  
        }; 
        
        // 返回树的高度
        int height(struct Node *N) 
        { 
            if (N == NULL) 
                return 0; 
            return N->height; 
        } 
        
        // 返回以结点 N 为根的树的大小
        int size(struct Node *N) 
        { 
            if (N == NULL) 
                return 0; 
            return N->size; 
        } 
        
        /* 创建一个结点 */
        struct Node* newNode(int key) 
        { 
            struct Node* node = new Node; 
            node->key = key; 
            node->left = node->right = NULL; 
            node->height = node->size = 1; 
            return(node); 
        } 
        
        // 右旋操作
        struct Node *rightRotate(struct Node *y) 
        { 
            struct Node *x = y->left; 
            struct Node *T2 = x->right; 
            
            x->right = y; 
            y->left = T2; 
        
            y->height = max(height(y->left), height(y->right))+1; 
            x->height = max(height(x->left), height(x->right))+1; 
        
            y->size = size(y->left) + size(y->right) + 1; 
            x->size = size(x->left) + size(x->right) + 1; 
            //返回新的根结点
            return x; 
        } 
        
        // 左旋操作
        struct Node *leftRotate(struct Node *x) 
        { 
            struct Node *y = x->right; 
            struct Node *T2 = y->left; 
        
            y->left = x; 
            x->right = T2; 
        
            x->height = max(height(x->left), height(x->right))+1; 
            y->height = max(height(y->left), height(y->right))+1; 
        
            x->size = size(x->left) + size(x->right) + 1; 
            y->size = size(y->left) + size(y->right) + 1; 
            // 返回新的根结点
            return y; 
        } 
        
        // 获取平衡因子 
        int getBalance(struct Node *N) 
        { 
            if (N == NULL) 
                return 0; 
            return height(N->left) - height(N->right); 
        } 
        
        // AVL插入操作
        struct Node* insert(struct Node* node, int key, int *result) 
        { 
            if (node == NULL) 
                return(newNode(key)); 
        
            if (key < node->key) 
            { 
                node->left  = insert(node->left, key, result); 
                *result = *result + size(node->right) + 1; 
            } 
            else
                node->right = insert(node->right, key, result); 
        
            node->height = max(height(node->left), 
                            height(node->right)) + 1; 
            node->size = size(node->left) + size(node->right) + 1; 
        
            int balance = getBalance(node); 
        
            if (balance > 1 && key < node->left->key) 
                return rightRotate(node); 
    
            if (balance < -1 && key > node->right->key) 
                return leftRotate(node); 
    
            if (balance > 1 && key > node->left->key) 
            { 
                node->left =  leftRotate(node->left); 
                return rightRotate(node); 
            } 
    
            if (balance < -1 && key < node->right->key) 
            { 
                node->right = rightRotate(node->right); 
                return leftRotate(node); 
            } 
            return node; 
        } 
    public:
        int reversePairs(vector<int>& nums) {
            struct Node *root = NULL; 
    
            int result = 0;   
    
            for (int i = 0; i< nums.size(); i++) 
            {
                root = insert(root, nums[i], &result); 
            }
            return result; 
        }  
    };

#### 复杂度分析 ####

*  时间复杂度：AVL树的插入操作的时间复杂度为，插入 n 个元素，所以总的时间复杂度就为量级。
 *  空间复杂度：.

不过我得承认，使用 AVL 实现逆序对的统计操作的未能 AC 力扣的所有测试用例，感兴趣的小伙伴可以自己尝试一下，但是这是一个不错的思想，你说呢？

最后给大家推荐一道类似的 LeetCode 题目，315. 计算右侧小于当前元素的个数 。解法可以使用上面提到各类方法，快去 AC 吧~~

\---

由 五分钟学算法 原班人马打造的公众号：图解面试算法，现已正式上线！
    接下来我们将会在该公众号上，为大家分享优质的算法解题思路，坚持每天一篇原创文章的输出，视频动画制作不易，感兴趣的小伙伴可以关注点赞一下哈！

[format_png]: /images/20230208/3539382bafcd46b882451e0216cb57dc.png
[format_png 1]: /images/20230208/0151948d2e5b4851b53cac597865db38.png
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzA4NDE4MzY2MA%3D%3D&idx=2&mid=2647522698&scene=21&sn=c933a80e36743389ae812ad9509f59cb#wechat_redirect
[format_png 2]: /images/20230208/f1e4c5cb81e94a539a33441aecb0ac37.png
[format_png 3]: /images/20230208/44d1d7c9d8724f50bfe779ad2c08985f.png
[format_png 4]: /images/20230208/7b63ee5d57ce44f08db0b4d6dd3b1391.png
[format_png 5]: /images/20230208/e972ef491aab4b2f9171cc21fd4ebcb0.png
[format_png 6]: /images/20230208/48c22ec810c844379786482169eb1c5b.png
[format_png 7]: /images/20230208/e4fc73effe384fdaa9ce14dc3a20534f.png
[Link 2]: https://mp.weixin.qq.com/s?__biz=MzA4NDE4MzY2MA%3D%3D&idx=1&mid=2647522825&scene=21&sn=302c27da39845ab4952a2de067cfdea8#wechat_redirect
[format_png 8]: /images/20230208/cc0466add678407fa5433b6d30db25ae.png
[format_png 9]: /images/20230208/51f9c0df500548d8923bf193b1026c00.png
[format_png 10]: /images/20230208/f9740727e51b401887fa2a80611ba0d5.png
[format_png 11]: /images/20230208/a063d9adc8824b94b634db7b88148e29.png
[format_png 12]: /images/20230208/0c3e47dea7564978b92888f4b378b193.png
[format_png 13]: /images/20230208/9ba98b3016c341a5b77c9b00e7db75d0.png
[format_png 14]: /images/20230208/04847ef1034446a48197ed7e5f48c693.png
[format_png 15]: /images/20230208/8a4da3d5dbc04b35b38f2ee60d88bdb6.png
[format_png 16]: /images/20230208/f39809a79d2043b39c233a7d1c9b297e.png
[format_png 17]: /images/20230208/f563b835fef94b17b06173831be1b6c5.png
[format_png 18]: /images/20230208/4fb4e743ba8f4b7695e54afde4fa40f8.png
[AVL]: https://mp.weixin.qq.com/s?__biz=MzA4NDE4MzY2MA%3D%3D&idx=1&mid=2647521381&scene=21&sn=796ac1eda0eaefadfb57a1b9742bcec0#wechat_redirect
[format_png 19]: /images/20230208/60731aa07a67462dad7c6015346a7066.png
[format_png 20]: /images/20230208/8cf72edc4a4d4de6a67ff5d7d9063a32.png
[format_png 21]: /images/20230208/7f58fa81945d4916b9ab3302ee9a792e.png
[format_png 22]: /images/20230208/fc7cb0a24092448798919d4986bf6999.png
[format_png 23]: /images/20230208/bc9f5ebd55bb42f79027393f9c2715cc.png