devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：IT小白 | 2024-03-23 03:54:48

赞

踩

字节跳动面试代码

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

重磅干货，第一时间送达

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

剑指 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。

示例

  1. 输入: arr[]={8，5，4，2，1}
  2. 输出: 10
  3. 解释: 逆序对为(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，前提是知道数组完全逆序
  4.  
  5. 输入: arr[]={5，1，4，2，8}
  6. 输出: 4
  7. 解释: 逆序对为(5，1)、(5，4)、(5，2)，还有(4，2)，总共4个。
  8. 在这里也可以看出数组{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 次不必要的比较操作，后面要讲的其他方法事实上就是努力将这种不必要的次数降到最低。

实现代码
  1. class Solution {
  2.     public int reversePairs(int[] nums) {
  3.         int count = 0;
  4.         int n = nums.length;
  5.         for(int i = 0;i < n - 1; i++){
  6.             for(int j = i+1; j < n; j++){
  7.                 if(nums[i] > nums[j]){
  8.                     count++;
  9.                 }
  10.             }
  11.         }
  12.         return count;
  13.     }
  14. }
复杂度分析

  • 时间复杂度：

  • 空间复杂度：

归并排序

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

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

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

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

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

第一步，合并 8 和 5 ，8 > 5 ，为一个逆序对，count = count + 1 = 1

第二步，合并 [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)  是为了保证边界的准确性。

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

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

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

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

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

实现代码
  1. class Solution {
  2.     //合并函数
  3.     private static int mergeAndCount(int[] arr, int l, int m, int r) 
  4.     { 
  5.         int[] left = Arrays.copyOfRange(arr, l, m + 1); 
  6.  
  7.         int[] right = Arrays.copyOfRange(arr, m + 1, r + 1); 
  8.   
  9.         int i = 0, j = 0, k = l, swaps = 0; 
  10.   
  11.         while (i < left.length && j < right.length) { 
  12.             if (left[i] <= right[j]) 
  13.                 arr[k++] = left[i++]; 
  14.             else { 
  15.                 arr[k++] = right[j++]; 
  16.                 swaps += (m + 1) - (l + i); 
  17.             } 
  18.         } 
  19.  
  20.         while (i < left.length) 
  21.             arr[k++] = left[i++]; 
  22.  
  23.         while (j < right.length) 
  24.             arr[k++] = right[j++]; 
  25.   
  26.         return swaps; 
  27.     } 
  28.   
  29.     // 归并排序
  30.     private static int mergeSortAndCount(int[] arr, int l, int r) 
  31.     { 
  32.         int count = 0; 
  33.   
  34.         if (l < r) { 
  35.             int m = (l + r) / 2; 
  36.   
  37.             count += mergeSortAndCount(arr, l, m); 
  38.  
  39.             count += mergeSortAndCount(arr, m + 1, r); 
  40.  
  41.             count += mergeAndCount(arr, l, m, r); 
  42.         } 
  43.   
  44.         return count; 
  45.     }     
  46.     public int reversePairs(int[] nums) {
  47.         return mergeSortAndCount(nums, 0, nums.length-1);
  48.     }
  49. }
复杂度分析

树状数组

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

之前写树状数组的文章时，我强调过树状数组的核心思想并不在 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 .

  1. static int getSum(int[] BITree, int index) 
  2. { 
  3.     int sum = 0; 
  4.     while (index > 0) 
  5.     { 
  6.         //将当前 BITree[] 的值加到 sum 中
  7.         sum += BITree[index]; 
  8.         //找到 index 的父结点
  9.         index -= index & (-index); 
  10.     } 
  11.     return sum; 
  12. } 

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

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

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

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

更新树状数组的函数：

  1. static void updateBIT(int[] BITree, int n, int index, int val) 
  2. { 
  3.     while (index <= n) 
  4.     { 
  5.         BITree[index] += val; 
  6.         index += index & (-index); 
  7.     } 
  8. }

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

具体为什么更新位置 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); 更新完之后树状数组如下所示：

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

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

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

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

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

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

第五步：下标 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); 更新完之后树状数组如下所示：

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

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

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

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

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

我想你现在应该清晰啦！

第二个问题：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[] 中的元素数目；

代码写起来很简单。

实现代码
  1. class Solution {
  2.     private static int getSum(int[] BITree, int index) 
  3.     { 
  4.         int sum = 0;
  5.         while(index > 0){
  6.             sum += BITree[index];
  7.             index -= index & (-index);
  8.         }
  9.  
  10.         return sum;
  11.     } 
  12.  
  13.     private static void updateBITree(int[] BITree, int n, 
  14.                                      int index, int val) 
  15.     { 
  16.         while(index <= n){
  17.             BITree[index] += val;
  18.             index += index & (-index);
  19.         }
  20.     }     
  21.     public int reversePairs(int[] nums) {
  22.         int count = 0;
  23.         int maxElement = 0;
  24.         int n = nums.length;
  25.         int[] arr = new int[n];
  26.         for(int i = 0; i < n; i++){
  27.             if(nums[i] > 0){
  28.                 arr[i] = nums[i];
  29.             }else{
  30.                 arr[i] = -nums[i];
  31.             }
  32.         }
  33.         for(int i = 0; i < n; i++){
  34.             if(arr[i] > maxElement){
  35.                 maxElement = arr[i];
  36.             }
  37.         }
  38.  
  39.         int[] BITree = new int[maxElement + 1];
  40.         for(int i = 0; i < BITree.length; i++){
  41.             BITree[i] = 0;
  42.         }
  43.         
  44.         for(int i = n - 1; i >= 0; i--){
  45.             count += getSum(BITree, arr[i] - 1);
  46.             updateBITree(BITree, maxElement, arr[i], 1);
  47.         }
  48.  
  49.         return count;
  50.     }
  51. }

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

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

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

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

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

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

  1. int a[] = {1,2,3,4};
  2. int *temp = (int *)a;
  3. int *p = temp + 2;
  4.  
  5. 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} .

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

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

接下来就是树状数组发挥作用的时候啦！

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

更新之后的树状数组为：

树状数组中的元素 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 .

实现代码
  1. class Solution {
  2.  
  3.     int getSum(int BITree[], int index){
  4.         int sum = 0;
  5.         while(index > 0){
  6.             sum += BITree[index];
  7.             index -= index & (-index);
  8.         }
  9.  
  10.         return sum;
  11.     }
  12.     void updateBIT(int BITree[], int n, int index, int val){
  13.         while(index <= n){
  14.             BITree[index] += val;
  15.             index += index & (-index);
  16.         }
  17.     }
  18.  
  19.     void convert(vector<int>& nums) 
  20.     { 
  21.         int n = nums.size();
  22.         int temp[n];
  23.         for(int i = 0; i < n; i++){
  24.             temp[i] = nums[i];
  25.         }
  26.         sort(temp, temp + n);
  27.  
  28.         for(int i = 0; i < n; i++){
  29.             nums[i] = lower_bound(temp, temp + n, nums[i]) - temp + 1;
  30.         }
  31.     } 
  32.  
  33. public:
  34.     int reversePairs(vector<int>& nums) {
  35.         int count = 0;
  36.         int n = nums.size();
  37.         if(n <= 0){
  38.             return count;
  39.         }
  40.         convert(nums);
  41.         int BITree[n + 1];
  42.         for(int i = 0; i <= n; i++){
  43.             BITree[i] = 0;
  44.         }
  45.  
  46.         for(int i = n - 1; i >= 0; i--){
  47.             count += getSum(BITree, nums[i] - 1);
  48.             updateBIT(BITree, n, nums[i], 1);
  49.         }
  50.  
  51.         return count;
  52.     }
  53. };
复杂度分析

  • 时间复杂度：updateBIT() 和 getSum() 的时间复杂度均为 ，而更新树状数组的函数 updateBIT() 被运行了 n 次，整个算法的时间复杂度为 .

  • 空间复杂度： ，需要空间为 n 的树状数组 BITree[] .

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

AVL平衡二叉树法

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

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

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

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

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

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

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

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

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

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

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

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

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

实现代码：
  1. class Solution {
  2.     // AVL 树的结点
  3.     struct Node 
  4.     { 
  5.         int key, height; 
  6.         struct Node *left, *right; 
  7.         //以 this.Node 为根的树的大小
  8.         int size;  
  9.     }; 
  10.     
  11.     // 返回树的高度
  12.     int height(struct Node *N) 
  13.     { 
  14.         if (N == NULL) 
  15.             return 0; 
  16.         return N->height; 
  17.     } 
  18.     
  19.     // 返回以结点 N 为根的树的大小
  20.     int size(struct Node *N) 
  21.     { 
  22.         if (N == NULL) 
  23.             return 0; 
  24.         return N->size; 
  25.     } 
  26.     
  27.     /* 创建一个结点 */
  28.     struct Node* newNode(int key) 
  29.     { 
  30.         struct Node* node = new Node; 
  31.         node->key = key; 
  32.         node->left = node->right = NULL; 
  33.         node->height = node->size = 1; 
  34.         return(node); 
  35.     } 
  36.     
  37.     // 右旋操作
  38.     struct Node *rightRotate(struct Node *y) 
  39.     { 
  40.         struct Node *x = y->left; 
  41.         struct Node *T2 = x->right; 
  42.         
  43.         x->right = y; 
  44.         y->left = T2; 
  45.     
  46.         y->height = max(height(y->left), height(y->right))+1; 
  47.         x->height = max(height(x->left), height(x->right))+1; 
  48.     
  49.         y->size = size(y->left) + size(y->right) + 1; 
  50.         x->size = size(x->left) + size(x->right) + 1; 
  51.         //返回新的根结点
  52.         return x; 
  53.     } 
  54.     
  55.     // 左旋操作
  56.     struct Node *leftRotate(struct Node *x) 
  57.     { 
  58.         struct Node *y = x->right; 
  59.         struct Node *T2 = y->left; 
  60.     
  61.         y->left = x; 
  62.         x->right = T2; 
  63.     
  64.         x->height = max(height(x->left), height(x->right))+1; 
  65.         y->height = max(height(y->left), height(y->right))+1; 
  66.     
  67.         x->size = size(x->left) + size(x->right) + 1; 
  68.         y->size = size(y->left) + size(y->right) + 1; 
  69.         // 返回新的根结点
  70.         return y; 
  71.     } 
  72.     
  73.     // 获取平衡因子 
  74.     int getBalance(struct Node *N) 
  75.     { 
  76.         if (N == NULL) 
  77.             return 0; 
  78.         return height(N->left) - height(N->right); 
  79.     } 
  80.     
  81.     // AVL插入操作
  82.     struct Node* insert(struct Node* node, int key, int *result) 
  83.     { 
  84.         if (node == NULL) 
  85.             return(newNode(key)); 
  86.     
  87.         if (key < node->key) 
  88.         { 
  89.             node->left  = insert(node->left, key, result); 
  90.             *result = *result + size(node->right) + 1; 
  91.         } 
  92.         else
  93.             node->right = insert(node->right, key, result); 
  94.     
  95.         node->height = max(height(node->left), 
  96.                         height(node->right)) + 1; 
  97.         node->size = size(node->left) + size(node->right) + 1; 
  98.     
  99.         int balance = getBalance(node); 
  100.     
  101.         if (balance > 1 && key < node->left->key) 
  102.             return rightRotate(node); 
  103.  
  104.         if (balance < -1 && key > node->right->key) 
  105.             return leftRotate(node); 
  106.  
  107.         if (balance > 1 && key > node->left->key) 
  108.         { 
  109.             node->left =  leftRotate(node->left); 
  110.             return rightRotate(node); 
  111.         } 
  112.  
  113.         if (balance < -1 && key < node->right->key) 
  114.         { 
  115.             node->right = rightRotate(node->right); 
  116.             return leftRotate(node); 
  117.         } 
  118.         return node; 
  119.     } 
  120. public:
  121.     int reversePairs(vector<int>& nums) {
  122.         struct Node *root = NULL; 
  123.  
  124.         int result = 0;   
  125.  
  126.         for (int i = 0; i< nums.size(); i++) 
  127.         {
  128.             root = insert(root, nums[i], &result); 
  129.         }
  130.         return result; 
  131.     }  
  132. };
复杂度分析

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

  • 空间复杂度： .

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

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

---

  1. 由 五分钟学算法 原班人马打造的公众号：图解面试算法，现已正式上线！
  2. 接下来我们将会在该公众号上，为大家分享优质的算法解题思路，坚持每天一篇原创文章的输出，视频动画制作不易，感兴趣的小伙伴可以关注点赞一下哈！
  3.
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/293012
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号