This is the 8th day of my participation in Gwen Challenge
Count the number of elements on the right that are less than the current element
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].
Thought analysis
J = I + 1 j <= size
Let’s take a closer look at the problem. Emmm is in reverse order
Unlike reverse pairs, which count only a total, this counts the number of elements to the right of each element that are less than the current element.
This is equivalent to setting up a table, map[val]idx, that records the number of elements to the right of each element that is less than the current element.
You can really use merge sort to compute inversions, right?
In the last article, I briefly introduced the correctness of the computation omitted by a merge, and we can avoid the n-square complexity of violence by taking advantage of local orderliness.
However, it is not proved in detail whether the number of inversions calculated after merging is correct.
Followed by [10,7,5,2,4,3,6,8]
Merge for the first time [10,7] [5,2] [4,3] [6,8]
The inversions of the calculation are: [10,7] [5,2] [4,3] [6,8]
Merge second: [7,10,2,5] [3,4,6,8]
Compute inversions: [2,7] [2, 10] [5,7] [5,10]
After merging twice, we can find the logic to get the inversion pair
When arr[m] < arr1[x] is merged, it must represent the inversions of arr[m] and arr1[x..size].
But then arr. Size is extremely small (say 2, or 4). But since ARR and ARR1 can change position no matter how much, arR2 will not be affected… Size over 2 merge. So they must be locally ordered at any time.
If we focus on the last arr, for example, [6,8], [3,4,6,8], each merge must add a number of values to compare with 8, such as the first 6, the second 3,4 (of course, 3,4 does not add inversions), and the third 7,10,2,5.
So a number can be understood as having been compared with all the other preceding numbers.