剛才我問豆包一個問題，中國加班最厲害的互聯網公司有哪些？結果他列出了拼多多，得物，字節，華為，阿里。。。我印象中也確實是這幾家加班比較多，甚至有的人入職之后，連和女朋友聯系的時間都沒有了，還問進入字節，是不是就只有工作沒有愛情了？

最近就有一網友，自從入職字節之后，每天早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多題，對算法題有自己獨特的解題思路和解題技巧。