Topic describes

Their thinking

  • When I first saw this problem, the first thing THAT came to my mind was the brute force solution, where I iterate through the for loop, and it timed out.
  • When you look at the solution, you usually solve inversions by merge sort
  • The essence of this question is still merge sort, but it just adds a line of code to merge sort.
  • Merge sort uses the idea of divide-and-conquer, and the question is based on whether or merge, statistical calculation, and finally get the result.

Solution code 1 (Brute force method: timeout)

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 the code

Problem solving code two (merge sort)

var reversePairs = function(nums) {
    / /! Use the idea of merge sort
    // Define the number of inversions that the variable stores
    let sum = 0;
    // The 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, indicating that there is only one element, we return the array, which is the end condition of the recursion
        if (nums.length < 2) return nums;
        // If the length of the array is not less than 2, the partition is not complete
        let mid = Math.floor(nums.length / 2);
        // The left subarray
        let left = nums.slice(0,mid);
        // The right subarray
        let right = nums.slice(mid);
        // Put the split left and right subarrays into the merge function
        return merge(mergeSort(left),mergeSort(right));
    }

    // Merge function (user merges subarrays)
    function merge(left,right) {
        // Define a total group that contains the 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 the loop based on the index of res (I is the index of the left subarray, j is the index of the right subtree group, index is the index of res)
        for (let i = 0,j = 0,index=0; index < leftLen + rightLen; index++) {// The following judgment should be made first of the transgression condition
            if (i >= leftLen) {
                // If I is out of bounds, the left subarray has been traversed, and res adds the right subarray's subindex to the element
                res.push(right[j++])
            } else if (j >= rightLen) {
                // If j is out of bounds, it indicates that the right subarray has been traversed. In this case, res simply adds the element pointed to by the left subarray
                res.push(left[i++]);
            } else if (left[i] <= right[j]) {
                // If the index of the left subarray is less than or equal to the index of the right subarray, then there are no inversions
                res.push(left[i++])
            } else {
                // If the subscript of the left subarray points to an element larger than the subscript of the right subarray, then there is an inversion pair
                res.push(right[j++]);
                sum = sum + leftLen - i
            }
        }
        // Return the merged array.
        returnres; }};Copy the code

Conclusion (this topic gives us the enlightenment of thinking)

  • Lesson 1: Learn to use merge sort
  • Lesson two: Learn to divide and conquer merge sort