35.数组中的逆序对

题目描述：

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof

知识点：

• 归并排序

解题思路：

• 这道题给我们一个数组要我们求其中逆序对的个数，我们采用类似于归并排序的思路来解决这道题
• 具体步骤为，我们首先需要让指针指向相邻的两个数字来划分出两个数组
• 我们让两个指针分别指向这两个数组的最右端
• 判断最右端两个数字的大小，将较大的那个放在数组中靠后的位置上
• 这样递归下来我们可以发现，左右两个数组都是按照升序排列的，如果左边数组最右边的元素大于右边数组最右端的元素那么，左边数组最右端的元素将大于右边数组中所有的数
• 如图所示，如果实在无法理解可以边看代码，边看图，以7,5,6,4为例理解

解题代码：

var reversePairs = function(nums) {
    return mergeSort(nums,0,nums.length-1,[]);
    function mergeSort(array,left,right,temp){
        if(left < right) {
            // 1.让指针指向相邻的两个元素，同时判断这两个元素是不是逆序对
            let mid = (left + right) >> 1;
            let l = mergeSort(array,left,mid,temp);
            let r = mergeSort(array, mid+1,right,temp);
            // 2.判断左右指针所指元素中一共有多少对逆序对
            let res = merge(array,left,right,mid,temp);
            return l + r + res;
        }else {
            return 0;
        }
    }
    function merge(array,left,right,mid,temp){
        let leftIndex = mid;
        let rightIndex = right;
        let tempIndex = right - left;
        let count = 0;
        while(leftIndex >= left && rightIndex > mid){
                console.log(array[leftIndex],array[rightIndex])
            if(array[leftIndex] > array[rightIndex]){
                count += (rightIndex - mid);
                temp[tempIndex--] = array[leftIndex--];
            }else {
                temp[tempIndex--] = array[rightIndex--];
            }
        }
        while(leftIndex >= left) {
            temp[tempIndex--] = array[leftIndex--];
        }
        while(rightIndex > mid) {
            temp[tempIndex--] = array[rightIndex--];
        }
        tempIndex = 0;
        for(let i = left;i<=right;i++) {
            array[i] = temp[tempIndex++]
        }
        return count;
    }
};