[B] [C] [D]

Two digits in an array form a reverse pair if the preceding digit is larger than the following digit. Enter an array and find the total number of inversions in the array.

Example 1:

Input: [7,5,6,4] output: 5Copy the code

Limitations:

0 <= Array length <= 50000

Their thinking

The simplest way to solve this problem is to create a double-layer loop and ensure that the index of the inner element is greater than that of the outer element. If the outer element is greater than that of the inner element, a reverse pair is formed to record the number. When the double loop is complete, you have all the inversions. There is no problem with such a solution, but after submission, it will be found that the time limit is exceeded, and the time complexity of O(n²) does not meet the requirements of this problem.

So what’s a more efficient way to do it? So here we can do merge sort. In the process of merge sort of back, will be about the combination of array, when this time choose to is on the right side of the elements in the array, if the left have not deal with element in the array, because of the position, before and after the left side of the array elements in the array elements on the right side, and when left untreated element values are bigger than the current element value, Therefore, each unprocessed element in the left array forms an inverse pair with the current element, and the number of such inversions is recorded. When angelica and sort backtracking is completed, the number of all inversions in the array is obtained.

The demo

Code implementation

Var reversePairs = function(nums) {var reversePairs = function(nums) {const len = nums.length, arr = Array(len); Function getCount(l,r){if(l>=r) return 0; Const mid = (l+r)>>1; // Let res = 0; Res += getCount(l,mid); Res += getCount(mid+1,r); // let k = l, I = l,j = mid+1; While (I < = mid | | j < = {if j > r (r) | | (I < = mid && nums [I] < = nums [j]) {arr = nums [k++] [i++]} else {/ / if the put is on the right side of the array elements, Arr [k++] = nums[j++] res += mid- I +1}} for(let I = l; i<=r; i++){ nums[i] = arr[i] } return res; Return getCount(0,len-1)};Copy the code

At this point we have completed the reverse pairs in the Leetcode – finger Offer 51- array

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