[B] [C] [D]

Given an integer array nums **, return a new array counts ** as required. Counts [I] is the number of elements to the right of nums[I] that are less than nums[I].

Example 1:

Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: there are two smaller elements to the right of 5 (2 and 1), there is only one smaller element to the right of 2 (1), there is one smaller element to the right of 6 (1), there are zero smaller elements to the right of 1Copy the code

Example 2:

Input: nums = [-1] Output: [0]Copy the code

Example 3:

Input: nums = [-1,-1] output: [0,0]Copy the code

Tip:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

Their thinking

The inner loop iterates through the elements behind the current element in the outer loop. If the inner loop is smaller than the current element, the value of the current element results in +1. This completes the inner loop, and we get the number of elements smaller to the right of the current element in the outer loop. But this is O(n ^ 2) time, so it doesn’t work. So how can we more efficiently figure out how many elements to the right of each element are smaller than that? So here we can use merge sort to solve this problem. Before merging sort and backward merging, we assume that the right interval elements are all smaller than the left interval elements, and add the number of the right interval elements to the corresponding result values of the left interval elements. During the merge process, when the left interval element is inserted into the result array, if there are unprocessed elements in the right interval at this time, they must be larger than the current left interval element. In this case, the number of unprocessed elements in the right interval should be subtracted from the corresponding result value of the current left interval element. Thus, we get the number of elements in the right interval that are smaller than the left interval during the current merge. When angelica is sorted, you get the number of smaller elements to the right of each element.

The demo

Code implementation

Var countSmaller = function(nums) {var countSmaller = function(nums) {const len = nums.length, // Create the subscript Array inds = Array(len), // initialize the result Array res = Array(len).fill(0); // initialize the subscript array for(let I = 0; i<len; i++){ inds[i] = i; } // Because we want to modify the current value at the corresponding index position in the result array // so, if we sort by values, Function mergeSort(l,r){if(l>=r) return; function mergeSort(l,r){if(l>=r) return; const mid = (l+r)>>1; MergeSort (l,mid) mergeSort(mid+1,r) // Before mergeSort(mid+1,r), assume that the right interval elements are all smaller than the left interval elements, add the number of right interval elements to the result value of the left interval elements. i<=mid; I++) {res [inds [I]] + = r - mid} / / back in the merging process let k = l, I = l, j = mid + 1 while (I < = mid | | j < = {if j > r (r) | | (I < = mid && Nums [inds[I]]<=nums[inds[j]])){ So give it the value minus the right interval residual element res [inds [I]] - = r - j + 1 \ [k++] = inds [i++]} else {\ [k++] = inds [j++]}} for (let I = l; i<=r; I ++){inds[I] = temp[I]}} mergeSort(0,len-1); };Copy the code

At this point we are done with Leetcode-315 – counting the number of elements on the right that are less than the current element

If you have any questions or suggestions, please leave a comment!