## Sword finger offer -- reverse order pair in array (JS Implementation)

Always_ positive 2021-05-03 13:20:55
sword finger offer reverse order

## Title Description ## Their thinking

• I'm just beginning to see the problem , The first thing that comes to mind is violence , That is, through for Loop through and through , Result timeout .
• Only after reading the explanation can we know , Solve the problem of reverse order , It's often sorted by merging
• The essence of this question is to merge and sort , Just on the basis of merging and sorting , It's just a line of code .
• Merging and sorting use the idea of divide and conquer , This question is based on the merger or not , Do statistical calculations , The final result is .

## Solution code one （ Violence law ： Overtime ）

``````var reversePairs = function(nums) {
let flag = 0;
for (let i = 0; i < nums.length; i++) {
const temp = nums.slice(i+1);
for (let v of temp) {
if (v < nums[i]) {
flag++;
}
}
}
return flag;
};
Copy code ``````

## Problem solving code 2 （ Merge sort ）

``````var reversePairs = function(nums) {
// ! Using the idea of merge sort
// Define the number of variable storage reverse pairs
let sum = 0;
// The return result of merge sort is assigned to sum
mergeSort(nums);
// Return the final result
return sum;
// Merge sort function
function mergeSort(nums) {
// If the length of the array is less than 2, When there is only one element , Let's return this array , The end condition of recursion
if (nums.length < 2) return nums;
// If the length of the array is not less than 2, The explanation is not complete yet , Let's continue to divide
let mid = Math.floor(nums.length / 2);
// The subarray on the left
let left = nums.slice(0,mid);
// The subarray on the right
let right = nums.slice(mid);
// Put the split left and right subarrays into the merge function
return merge(mergeSort(left),mergeSort(right));
}
// Merge functions （ The user merges the split subarrays ）
function merge(left,right) {
// Define a total array to store, merge, and order （ Containing left and right subarrays ）
const res = [];
// The length of the left subarray
const leftLen = left.length;
// The length of the right subarray
const rightLen = right.length;
// Start loop traversal , In order to res Based on the subscript of (i Is the subscript of the left subarray ,j Is the subscript of the right subtree group ,index yes res The subscript )
for (let i = 0,j = 0,index=0;index < leftLen + rightLen; index++) {
// In the following judgment, we should first judge the condition of crossing the boundary
if (i >= leftLen) {
// If i Cross border explanation , The left subarray has been traversed , here res Directly add the element pointed by the subscript of the right subarray
res.push(right[j++])
} else if (j >= rightLen) {
// If j Transboundary , Indicates that the right subarray has been traversed , here res Directly add the element pointed by the subscript of the left subarray
res.push(left[i++]);
} else if (left[i] <= right[j]) {
// If the element pointed to by the left subarray subscript is less than or equal to the element pointed to by the right subarray subscript , There is no reverse order pair at this time , Add the result of the left subarray to res The array can be
res.push(left[i++])
} else {
// If the left subarray subscript points to more elements than the right subarray subscript points to , There is a reverse order pair
res.push(right[j++]);
sum = sum + leftLen - i
}
}
// Returns the merged array （ It's easy to make mistakes here ）
return res;
}
};
Copy code ``````

## summary （ The inspiration of this topic to us ）

• Revelation 1 ： Learn to use merge sort
• Revelation 2 ： Learn to merge and sort the thought of divide and rule

https://qdmana.com/2021/05/20210503131221993o.html