315.计算右侧小于当前元素的个数

题目

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
示例：

输入： nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

提示：

• 0 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

  思路

  其实除了暴力没有特别好的思路，后来看了看别人的题解，自己又写了一遍。

  整体思路

  对下标进行归并排序，并且在排序时记录下每个位置后面数字的个数

  详细思路

  首先对整个数组进行归并。
  在每个归并段内，通过比较nums[idx[i]]来对idx[i]进行归并排序。并且在排序出现：nums[idx[i]]>nums[idx[j]]的时候，在idx[i]这个位置对应的最终结果（也即比nums中下标为idx[i]的元素右侧比这个元素大的元素个数）上面，加上该归并段内比nums[idx]大的数的个数：e-j+1。

  代码

  class Solution {
  public:
      vector<int> countSmaller(vector<int>& nums) {
          int n = nums.size();
          vector<int> res(n,0),helper(n,0),idxs(n,0);
          for(int i=0;i<n;i++) idxs[i] = i;
          mergeAndSort(nums,res,idxs,helper,0,n-1);
          return res;
      }
      void mergeAndSort(vector<int>& nums,vector<int>& res,vector<int>& idxs,vector<int>& helper,int s,int e){
          if(s>=e) return;
          int mid = s+(e-s)/2;
          mergeAndSort(nums,res,idxs,helper,s,mid);
          mergeAndSort(nums,res,idxs,helper,mid+1,e);
          mergeAndCount(nums,res,idxs,helper,s,mid,e);
      }
      void mergeAndCount(vector<int>& nums,vector<int>& res,vector<int>& idxs,
      vector<int>& helper,int s,int mid,int e){
          for(int i=s;i<=e;i++){
              helper[i] = idxs[i];
          }
          int i=s,j=mid+1,idx=s;
          while(i<=mid&&j<=e){
              if(nums[helper[i]]<=nums[helper[j]]){
                  idxs[idx++] = helper[j++];
              }else{
                  res[helper[i]]+= e-j+1;
                  idxs[idx++]=helper[i++];
              }
          }
          while(i<=mid){
              idxs[idx++] = helper[i++];
          }
          while(j<=e){
              idxs[idx++] = helper[j++];
          }
      }
  };