算法分析与设计第七次作业（leetcode 中 Count of Smaller Numbers After Self 和 Count of Range Sum 题解）

心得体会

这周做了几个graph的题目感觉都不是很难，其中 K-Similar Strings 这个题就是一个简单的BFS；Couples Holding Hands 就更加简单了，连BFS都不要，排个序就好了；Similar String Groups 这个有点意思，不过在之前的 算法设计与分析第二次作业 这篇博客里面我们已经了解过union find了，这道题目做起来也就不难了；
所以还是想要说一下之前的博客提到的两道题 Count of Smaller Numbers After Self 和 Count of Range Sum，这两道题十分巧妙利用mergesort算法，对其进行变式求解问题，需要相当的思考，所以自己还是选择对这两个题目做出归纳整理。
因为 Count of Smaller Numbers After Self 和 Count of Range Sum 两个题目求解技巧相似，所以整理到同一篇博客，详细情况见题解正文。

题解正文

题目描述

• Count of Smaller Numbers After Self：
  
• Count of Range Sum：
  

问题分析

Count of Smaller Numbers After Self 题目中给出一个数组，要求求出每个元素右边小于它的元素个数；
Count of Range Sum 题目也给出一个数组和一个区间，并记录数组中连续数字求和落在给定区间的情况，要求输出记录的个数；

解题思路

• 这两个题目都是要计数，并且我们可以轻松的想出naive的解法：对数组进行两层遍历，外层遍历数组中元素nums[i]，i从0到size-1，内层遍历数组中的元素nums[j]，j从i+1到size-1，然后根据两道题目相应的规则来计数：

  • 对于第一题，如果nums[i]>nums[j]，count[i]++；
  • 对于第二题，如果$lower \le \sum_{k=i}^j nums[k] \le upper$lower≤∑k=ij​nums[k]≤upper，则count++；

  但是毫无疑问，这样做的复杂度是$O(n^2)$O(n2)，会超时，第二题甚至明确要求复杂度优于$O(n^2)$O(n2)，所以只能想其它的方法。

• 复杂度有没有可能是$O(n)$O(n)----不可能，因为遍历一次无法完成计数，因为遍历一次只能取一个对象，没办法进行比较，所以我们能想到的是$O(nlog(n))$O(nlog(n))，我们需要考虑内层的$O(log(n)$O(log(n)，因为外层肯定是$O(n)$O(n)了，能做到$O(log(n))的算法也很多，树、堆、归并排序的merge操作等等，关键是如何结合具体问题加以利用。

• 这时我们看到第一个题，换个角度可能更有利于算法设计：我们对nums数组做一个稳定排序，排序过程中发生的每一个交换，就表明被换到前面的元素比被换到后面的元素小，这时候就可以递增被换到后面的元素的计数器，排序完成就得到最后的count数组，也就是答案，于是简单的得到如下伪代码：

  进行若干轮次稳定排序
  	每一轮次排序中，对于所有交换到前面的元素
  		遍历它超过的元素，递增被超过元素的计数器
  

  按照上面那样做，有三层循环，并且最内层并不是$O(1)$O(1)的，因为某个元素越过的元素可以是$O(n)$O(n)个，所以需要换一个思路来降低复杂度（遍历被交换到后面的元素）：

  进行若干轮次稳定排序
  	每一轮次排序中，对于所有交换到后面的元素nums[origin_index]
  		count[origin_index]+=
  		新一轮排序队列中位于nums[origin_index]元素前面的元素个数
  		-前一轮排序队列中位于nums[origin_index]元素前面的元素个数；
  

  上面的伪代码中只有两层循环，并且最内层循环的复杂度是$O(1)$O(1)的，因为这只是一个加减法操作，这个操作的含义是，求出这一轮排序中越过元素nums[origin_index]的元素个数，它等于新一轮排序队列中位于nums[origin_index]元素前面的元素个数减去前一轮排序队列中位于nums[origin_index]元素前面的元素个数。除此之外我们需要维护origin_index，表示该元素在原始nums中的位置。
  能够达到$O(nlog(n))$O(nlog(n))复杂度的稳定排序就是归并排序了，所以使用上述策略对归并排序修改即可。

• 对于第二个题，我们是否也能够试着使用归并排序的变式呢，因为做完Count of Smaller Numbers After Self，紧接在就做了第二题，刚好也要求优于$O(n^2)$O(n2)的复杂度，所以也从这个角度考虑一下。

  • 现在我们已经准备使用归并排序的变式求解问题了，所以第一个要做的事情就是确认排序对象：
    • 如果简单选取nums数组中的元素作为排序对象，是没有什么意义的，并且这样排序之后反而没办法做求和了（因为大小排序之后，位置就乱了，然后就没法对连续位置的元素求和了，然后题目就做不下去了）。
    • 所以这时应该换个角度看原问题，我们可以先做$\sum_{k=0}^inums[k]$∑k=0i​nums[k]的求和，并将每一项记为$sum[i]$sum[i]，然后计算$\sum_{k=i}^j nums[k]$∑k=ij​nums[k]可以通过作差得到：
      $\sum_{k=i}^j nums[k]=sum[j]-sum[i]=\sum_{k=0}^j nums[k]-\sum_{k=0}^i nums[k]$∑k=ij​nums[k]=sum[j]−sum[i]=∑k=0j​nums[k]−∑k=0i​nums[k]
      将sun[i]作为排序对象，这时排序才有意义：
      我们可以通过找出上下界元素然后将它们的下标作差来求出计数值，而不用遍历，从而大大减少复杂度。
      这里突然说到上下界元素可能有点突兀，下面将给出解释：
      我们要求的是所有的$\sum_{k=i}^j nums[k]$∑k=ij​nums[k]，它们满足
      $lower \le \sum_{k=i}^j nums[k]=sum[j]-sum[i]=\sum_{k=0}^j nums[k]-\sum_{k=0}^i nums[k] \le upper$lower≤∑k=ij​nums[k]=sum[j]−sum[i]=∑k=0j​nums[k]−∑k=0i​nums[k]≤upper
      => $lower + \sum_{k=0}^i nums[k] \le\sum_{k=0}^j nums[k] \le \sum_{k=0}^i nums[k] + upper$lower+∑k=0i​nums[k]≤∑k=0j​nums[k]≤∑k=0i​nums[k]+upper
      上面所谓的上下界就是这里的$lower + \sum_{k=0}^i nums[k]$lower+∑k=0i​nums[k]和$upper + \sum_{k=0}^i nums[k]$upper+∑k=0i​nums[k]，我们在外层遍历下标i的时候，将i作为求和的起点，我们希望找到终点j，使得求和结果在[lower，upper]之内，这就等价于找出所有的j，使得$下界\le \sum_{k=0}^j nums[k]=sum[j] \le 上界$下界≤∑k=0j​nums[k]=sum[j]≤上界，这样的sum[i]中最小的就是下界元素（记为nums[l]），最大的就是上界元素（记为nums[u]）。
      然后这时候排序的作用就体现出来了：
      如果所有能够作为终点的元素都排好序了，我们可以很简单的通过$count=count+u-l$count=count+u−l 来实现对count的计数。
  • 确认排序对象之后我们可以考虑更多的细节实现：
    按照上面的分析，我们已经确认使用归并排序，并且决定对sum排序。
    而我们实际上需要的是：
    遍历外层的下标i，将i作为求和的起点，然后从已经排好序的终点队列找出上下界，作差并计入count即可。
    那么问题来了----终点队列是什么：
    下标i的终点队列是原始nums数组中，位于i之后的所有下标组成的集合，也就是{i+1,i+2,…，n-2,n-1}，我们并不能在归并排序中一次性得到某个i的所有终点，怎么办呢，，，我们也不需要一次性得到所有终点啊，因为我们的归并排序也不是一次性就排好的啊。不难注意到，每次归并过程我们会合并两个有序序列，前一个序列元素在原始数组中的下标origin_index一定都小于后一个序列元素在原始数组中的下标origin_index，也就是说后者是终点队列的一个子集，所以我们对于每一个新插入归并队列的前一个序列中的元素，求出前面说到的上下界，然后在后一个序列中找到对应的上下界元素下标，作差计入count。我们对于自底向上的log(n)层归并操作，反复上述操作，就能够遍历完每个下标i后面的所有下标集合了，最后得到的count值，就是答案。

算法步骤

• Count of Smaller Numbers After Self：

  求解函数：
  	完成初始化（count数组），为数组nums维护一个下标数组indexes，在后续排序时将下标跟随数值排序；
  	调用mergesort(nums)；
  	输出count数组；
  
  mergesort函数（参数是一个待排序列）：
  	如果序列长度小于等于1，直接退出函数；
  	将序列二分，递归调用两个mergesort对分出来的两个序列排序；
  	使用merge函数归并上面第二步二分得到的两个序列；
  
  merge函数（参数是2个已经排好序的序列）：
  	遍历两个待归并序列A，B：
  		如果A序列队首元素更小：
  			count[indexes[i]]计数器更新为 count[indexes[i]]
  			+新一轮排序队列中位于nums[origin_index]元素前面的元素个数
  			-前一轮排序队列中位于nums[origin_index]元素前面的元素个数；
  			将A序列队首元素放入归并结果队列尾部，并且indexes数组对应位置也做同样的操作；
  		反之：
  			将B序列队首元素放入归并结果队列尾部，并且indexes数组对应位置也做同样的操作；
  	将原来的序列替换为归并结果（原来是将一个序列二分了，现在使用归并结果替代二分前序列）；
  

• Count of Range Sum：

  求解函数：
  	根据nums数组创建sums数组，sums[i]=nums[0]+nums[1]+...+nums[i-1]+nums[i]；
  	调用mergesort(sums)，对sums数组进行排序；
  	输出count；
  
  mergesort函数（参数是一个待排序列）：
  	如果序列长度小于等于1：
  		如果序列长度等于1，并且序列后一个元素和前一个元素之差是在[lower，upper]区间之内（记第一个元素的前一个元素是0）：
  			count递增1；
  		退出函数；
  	将序列二分，递归调用两个mergesort对分出来的两个序列排序；
  	使用merge函数归并上面第二步二分得到的两个序列（前半部分作为第一个参数，后一个作为第二个参数）；
  
  merge函数（参数是2个已经排好序的序列A，B）：
  	遍历两个待归并序列A，B：
  		如果A序列队首元素sums[i]比B序列当前对首元素更小：
  			计算符合题意的B序列元素sums[j]的上界下界：lower+sums[i]、upper+sums[i]；
  			从上一次找到的上下界元素下标开始递增，找到B序列中第一个大于下界的元素下标l，第一个大于上界的元素下标u；
  			count计数器更count+u-l；
  			将A序列队首元素放入归并结果队列尾部；
  		反之：
  			将B序列队首元素放入归并结果队列尾部；
  	将原来的序列替换为归并结果（原来是将一个序列二分了，现在使用归并结果替代二分前序列）；
  

复杂度分析

因为两个题目的做法都是对归并排序做一个变式，所以复杂度自然是$O(nlog(n))$O(nlog(n))，具体解释如下：

• Count of Smaller Numbers After Self：
  mergesort归并排序进行不断二分，然后不断归并，外层一共log(n)层，因为二分了log(n)次，所以归并的时候也是log(n)层归并，每一层归并使得有序序列个数变为上一层的一半，最终得到一个有序序列；
  merge归并过程，每一层的归并都进行了n次比较、n次插入和小于n次的更新count数组操作（这个操作是O(1)复杂度，因为只涉及个位数加减法操作，并且仅当前置位的序列队首元素比后置位序列的队首元素时更新count数组），因为归并过程就是合并两个已排序序列，然后该层所有前置位、后置位数组元素个数加起来就是n，因此归并过程复杂度O(n)；
  综上所述，该算法复杂度O(nlog(n))。
• Count of Range Sum：
  二分过程和上面的分析一样，一共分了log(n)层，只是内层操作不同；
  merge归并过程，每一层的归并都进行了n次比较、n次插入、小于n次的上下界查找，为什么上下界更新是小于n次的呢，看起来是写了一个内层循环，但是其实递增的次数是小于n次的，因为前置序列遍历过程中，数值是增加的，所以对应后置序列中上下界数值也是增加的，所以上下界查找的时候只需要递增下标就能找到下一个上下界元素（不可能需要下标回退的，回退的话意味着上下界数值的减小，与假设相悖），而因为上下界是在后置序列中查找的，后置序列中元素个数少于n，所以这个查找操作（递增操作）最多做小于n次；即该步骤复杂度O(n)
  综上所述，该算法复杂度O(nlog(n))。

代码实现&结果分析

• Count of Smaller Numbers After Self：
  代码实现

  class Solution {
  public:
      vector<int> countSmaller(vector<int>& nums) {
          vector<int> res(nums.size(), 0);
          vector<pair<int, int>> numsAndOrder(nums.size(), {0,0});
          for (int i = 0; i < nums.size(); ++i) {
              numsAndOrder[i] = {nums[i], i};
          }
          mergesort(res, numsAndOrder, 0, nums.size()-1);
          return res;
      }
  
      void mergesort(vector<int>& res, vector<pair<int,int>>& numsAndOrder, int start, int end) {
          if (start >= end) return;
          int mid = (start+end)/2;
          mergesort(res, numsAndOrder, start, mid);
          mergesort(res, numsAndOrder, mid+1, end);
          merge(res, numsAndOrder, start, mid, end);
      }
  
      void merge(vector<int>& res, vector<pair<int,int>>& numsAndOrder, int start, int mid, int end) {
          int i = start;
          int j = mid+1;
          int k = 0;
          pair<int,int> temp[end-start+1] = {};
          while (i!= mid+1 && j != end+1) {
              if (numsAndOrder[i].first <= numsAndOrder[j].first) {
                  res[numsAndOrder[i].second] += k-(i-start);
                  temp[k++] = numsAndOrder[i++];
              } else {
                  temp[k++] = numsAndOrder[j++];
              }
          }
  
          if (i == mid+1) {
              while (j != end+1) {
                  temp[k++] = numsAndOrder[j++];
              }
          } else {
              while (i != mid+1) {
                  res[numsAndOrder[i].second] += k-(i-start);
                  temp[k++] = numsAndOrder[i++];
              }
          }
  
          for (int i = 0; i < end-start+1; ++i) {
              numsAndOrder[start+i] = temp[i];
          }
      }
  };
  

  提交运行结果：

• Count of Range Sum：
  代码实现：

  class Solution {
  public:
      vector<long> nums;
      int Nsize;
      int lower;
      int upper;
      int count;
  
      int countRangeSum(vector<int>& nums, int lower, int upper) {
          if (nums.size() == 0 || lower > upper) {
              return 0;
          }
          this->nums = vector<long>(nums.size(), 0);
          (this->nums)[0] = long(nums[0]);
          for (int i = 1; i < nums.size(); ++i)
          {
              (this->nums)[i] = long(nums[i])+(this->nums)[i-1];
          }
  
          this->Nsize = nums.size();
          this->lower = lower;
          this->upper = upper;
          count = 0;
  
          mergesort(0, Nsize-1);
          return count;
      }
  
      void mergesort(int start, int end) {
          if (start >= end) {
              if (start == end && nums[start] <= upper && nums[start] >= lower) {
  //                cout << count << "+=" << '1' << endl;
                  count++;
              }
              return;
          }
          int mid = (start+end)/2;
          mergesort(start, mid);
          mergesort(mid+1, end);
          merge(start, mid, end);
      }
  
      void merge(int start, int mid, int end) {
          int i = start;
          int j = mid+1;
          int k = 0;
          long leftEdge = nums[start]+long(lower), rightEdge = nums[start]+long(upper);
          int l = mid+1, r = 0;
          while (l <= end && nums[l] < leftEdge) {
              l++;
          }
          r = l;
          while (r <= end && nums[r] <= rightEdge) {
              r++;
          }
  
          long temp[end-start+1] = {};
  
          while (i != mid+1 || j != end+1) {
              if (i != mid+1 && j != end+1&&nums[i] <= nums[j] || j == end+1) {
                  while (l <= end && nums[l] < leftEdge) {
                      l++;
                  }
                  r = r > l ? r : l;
                  while (r <= end && nums[r] <= rightEdge) {
                      r++;
                  }
                  //cout << "leftnum:" << nums[i] << " " << count << "+=" << r-l << endl;
                  count+=r-l;
                  temp[k++] = nums[i++];
                  leftEdge = nums[i] + lower;
                  rightEdge = nums[i] + upper;
              } else {
                  temp[k++] = nums[j++];
              }
          }
  
          for (int i = 0; i < end-start+1; ++i)
          {
              nums[i+start] = temp[i];
          }
      }
  };
  

  提交运行结果：