LeetCode—剑指 Offer 51. 数组中的逆序对

剑指 Offer 51. 数组中的逆序对

题目描述：
[51]
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

考察重点：
第51题归并排序实现。在排序过程中，比较左右两数组元素大小时，计算逆序对个数。

第51题

class Solution {
    
    int count = 0;
    public int reversePairs(int[] nums) {
    
        mergeSort(nums, 0, nums.length - 1);
        return count;
    }
    public void mergeSort(int[] nums, int left, int right){
    
        if(left >= right)   return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    public void merge(int[] nums, int left, int mid, int right){
    
        int[] numsTemp = new int[right - left + 1];
        int pointTemp = 0, pointR = mid + 1, pointL = left;
        while(pointL <= mid || pointR <= right){
    
            if(pointR > right || pointL > mid){
    
                while(pointL <= mid){
    
                    numsTemp[pointTemp++] = nums[pointL ++];
                }
                while(pointR <= right){
    
                    numsTemp[pointTemp++] = nums[pointR ++];
                }
                break;
            }
            if(nums[pointL] > nums[pointR]){
    
                count += (mid - pointL + 1);
                numsTemp[pointTemp ++] = nums[pointR++];
            }else{
    
                numsTemp[pointTemp ++] = nums[pointL++];
            }
        }
        for(int i = left;i <= right;i ++){
    
            nums[i] = numsTemp[i - left];
        }
    }
}