女友问我为什么进字节后不理她了，是不是一进字节就没爱情了？

刚才我问豆包一个问题，中国加班最厉害的互联网公司有哪些？结果他列出了拼多多，得物，字节，华为，阿里。。。我印象中也确实是这几家加班比较多，甚至有的人入职之后，连和女朋友联系的时间都没有了，还问进入字节，是不是就只有工作没有爱情了？

最近就有一网友，自从入职字节之后，每天早10晚11的，目前状态很差，女友还问他为什么在进入字节之后就不理她了。就这加班程度，估计回去倒头就睡，字节能不能跳都无所谓，只要心脏还能跳就行。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第315题：计算右侧小于当前元素的个数，难度是困难。

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

示例1：

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

示例2：

输入：nums = [-1,-1] 输出：[0,0]

• 1 <= nums.length <= 10^5

• -10^4 <= nums[i] <= 10^4

问题分析

这题让计算数组中每一个元素右边有多少比它小的元素，看似很简单的一道题，实则不容易，因为数组的长度有可能比较大，如果一个个计算，肯定会超时。

这题我们可以参考归并排序的思路，归并排序的思想是每次把数组分成两部分，一直分下去，直到不能分为止，然后在合并，合并的时候实际上是合并两个有序数组。

既然合并的两个数组是有序的，那么这题就好办了，我们选择从大往小合并，也就是先合并大的 ，在合并小的，如果前面的元素大于后面的元素，那么前面的元素一定大于后面元素之前的所有元素，有点绕，没关系，我们举个例子，比如我们要合并下面两个有序数组。

[2,4,5,8,9]和[1,3,6,10]

当前面的 8 和后面的 6 比较的时候，因为前面的 8 比后面的 6 大，所以 8 一定大于 6 以及它之前的所有元素，它的个数是 3 ，我们只需要累加即可。

这里在计算之前需要把数组转化一下，因为数组合并的时候位置会发生变化，我们需要先记录下每个元素的值和它对应的下标，代码如下。

JAVA：

public List   countSmaller(int[] nums) {     int n = nums.length;     int[] res = newint[n];// 计算的结果     int[][] arr = newint[n][2];// 记录原数组的值和下标     for (int i = 0; i < n; i++)         arr[i] = newint[]{nums[i], i};     mergeSort(arr, 0, n - 1, res);// 归并排序     // 把数组转成list集合     List ans =  new ArrayList<>(n);     for (int num : res)         ans.add(num);     return ans; } public void mergeSort(int[][] arr, int left, int right, int[] res) {     if (left < right) {         int mid = (left + right) >>> 1;         mergeSort(arr, left, mid, res);// 递归左边部分。         mergeSort(arr, mid + 1, right, res);// 递归右边部分。         merge(arr, left, mid, right, res);//  合并     } } // 合并两个有序的数组，从后往前开始合并。 // 前面数组范围[left,center]，后面数组的范围[center+1,right]。 private void merge(int[][] arr, int left, int center, int right, int[] res) {     int len = right - left + 1;// 两个子数组的总长度。     int[][] tmp = newint[len][2];     int index = len - 1;     int end1 = center;// 前面数组末尾的位置。     int end2 = right;// 后面数组末尾的位置。     // 使用双指针合并两个有序数组，从后往前合并。     while (end1 >= left && end2 > center) {         if (arr[end1][0] <= arr[end2][0]) {             tmp[index--] = arr[end2--];         } else {// 累加右侧小于当前元素的个数             res[arr[end1][1]] += end2 - center;             tmp[index--] = arr[end1--];         }     }     // 如果第一个数组前面还有数字就把他添加到临时数组中。     while (end1 >= left)         tmp[index--] = arr[end1--];     // 同理，如果第二个数组后面还有数字就把他添加到临时数组中。     while (end2 > center)         tmp[index--] = arr[end2--];     // 把临时数组中的元素放回原数组。     index = 0;     while (index < len)         arr[left + index] = tmp[index++]; }

C++：

public:     vector
               
  countSmaller(vector
                  
 &nums) {         int n = nums.size();         vector
                    
  res(n, 0); // 计算的结果         vector int ,  int >>  arr (n) ; // 记录原数组的值和下标         for (int i = 0; i < n; i++)             arr[i] = {nums[i], i};         mergeSort(arr, 0, n - 1, res); // 归并排序         return res;     }     void mergeSort(vector int ,  int >> &arr,  int  left,  int  right,  vector < int > &res)  {         if (left < right) {             int mid = left + (right - left) / 2;             mergeSort(arr, left, mid, res); // 递归左边部分             mergeSort(arr, mid + 1, right, res); // 递归右边部分             merge(arr, left, mid, right, res); // 合并         }     }     // 合并两个有序的数组，从后往前开始合并     // 前面数组范围[left,center]，后面数组的范围[center+1,right]     void merge(vector int ,  int >> &arr,  int  left,  int  center,  int  right,  vector < int > &res)  {         int len = right - left + 1; // 两个子数组的总长度         vector int ,  int >>  tmp (len) ;         int index = len - 1;         int end1 = center; // 前面数组末尾的位置         int end2 = right; // 后面数组末尾的位置         // 使用双指针合并两个有序数组，从后往前合并         while (end1 >= left && end2 > center) {             if (arr[end1].first <= arr[end2].first) {                 tmp[index--] = arr[end2--];             } else { // 累加右侧小于当前元素的个数                 res[arr[end1].second] += end2 - center;                 tmp[index--] = arr[end1--];             }         }         // 如果第一个数组前面还有数字就把他添加到临时数组中         while (end1 >= left)             tmp[index--] = arr[end1--];         // 同理，如果第二个数组后面还有数字就把他添加到临时数组中         while (end2 > center)             tmp[index--] = arr[end2--];         // 把临时数组中的元素放回原数组         for (int i = 0; i < len; i++) {             arr[left + i] = tmp[i];         }     }
          
         
       

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解900多题，对算法题有自己独特的解题思路和解题技巧。