Li Kou sword finger offer 51. reverse order pairs in the array

This article has participated in 「 New people's creation ceremony 」 Activities , Start the road of nuggets creation together .

Title source ：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

General meaning ：
Given an array , Find the number of reverse pairs in the array , The reverse pair is defined as ：

• Equipped with i < j, if nums[i] > nums[j] be nums[i] And nums[j] Form an inverse pair of

Ideas

If there are two ascending arrays nums1 and nums2, So how to compare the number of reverse pairs after the combination of these two ascending arrays ？

1. First , Because the two arrays themselves are ascending arrays , So there is no reverse order pair in the array itself
2. that , The number of reverse pairs after the combination of these two ascending arrays depends on how many elements in the previous array are larger than the latter array

Use double pointer i and j Respectively represent the traversal positions of two ascending arrays

if nums1[i] Greater than nums2[j], that i To the end of the previous array, all elements are greater than nums2[j], These elements are associated with nums2[j] Form an inverse pair of , Count the number and move the pointer back j;

if nums1[i] No more than nums2[j], So the pointer i Move backward

Through the above method, the number of reverse pairs of two ascending arrays can be counted , What if the two arrays are not in ascending order ？

That is, if there are two arrays nums1 and nums2, So how to compare the number of reverse pairs after the combination of these two arrays ？

1. First , Statistics nums1 and nums2 The number of pairs in reverse order , Then sort the two arrays
2. Calculate the number of reverse pairs after the combination of two ascending arrays according to the above method

So we can use the idea of merging and sorting , Calculate the number of pairs in reverse order while merging and sorting

See code for details ：

public int reversePairs(int[] nums) {
    
        int n = nums.length;
        return merge(nums, new int[n], 0, n - 1);
    }

    /** *  Merge sort , return  [left, right]  The number of inverse pairs in the interval  * @param nums * @param temp * @param left * @param right * @return */
    public int merge(int[] nums, int[] temp, int left, int right) {
    
        if (left >= right) {
    
            return 0;
        }
        int mid = (left + right) >> 1;
        //  Merge sort left half 
        int leftCount = merge(nums, temp, left, mid);
        //  Merge and sort the right half 
        int rightCount = merge(nums, temp, mid + 1, right);
        //  The largest element in the left half is not greater than the smallest element in the right half , It is proved that there will be no new reverse order pairs after the merging of two intervals 
        if (nums[mid] <= nums[mid + 1]) {
    
            return leftCount + rightCount;
        }
        //  Merge the left and right intervals and calculate the reverse order pair generated by the merge 
        int crossCOunt = mergeAndCount(nums, temp, left, right);
        return leftCount + rightCount + crossCOunt;
    }

    /** *  Combine the two intervals and calculate the reverse order pair generated by the combination  * * @param nums * @param temp * @param left * @param right * @return */
    public int mergeAndCount(int[] nums, int[] temp, int left, int right) {
    
        //  First, copy the merged interval elements to the temporary array 
        for (int i = left; i <= right; i++) {
    
            temp[i] = nums[i];
        }
        //  Left and right section boundaries 
        int mid = (left + right) >> 1;
        //  Make right pointer 
        int leftIdx = left;
        int rightIdx = mid + 1;
        //  Number of pairs in reverse order 
        int count = 0;
        //  Merge range 
        for (int i = left; i <= right; i++) {
    
            if (leftIdx == mid + 1) {
    
                nums[i] = temp[rightIdx++];
            } else if (rightIdx == right + 1) {
    
                nums[i] = temp[leftIdx++];
            } else if (temp[leftIdx] <= temp[rightIdx]) {
    
                nums[i] = temp[leftIdx++];
            } else {
        //  The current element of the left pointer is larger than the current element of the right pointer , Count the number of pairs in reverse order 
                count += mid - leftIdx + 1;
                nums[i] = temp[rightIdx++];
            }
        }
        return count;
    }