题解 | #数组中的逆序对#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
 */
let count = 0
export function InversePairs(nums: number[]): number {
    //暴力解法
    // // write code here
    // let count = 0
    // for(let i = 0;i < nums.length;i++){
    //     let arr = nums.slice(0,i)
    //     for(let j = 0;j <arr.length;j++){
    //         if(arr[j] > nums[i]){
    //             count++
    //         }
    //     }
    // }
    // return count

    //归并排序
    
    if(nums.length < 2)return 0
    //否则进入归并
    mergeSort(nums,0,nums.length-1)
    return count
}
const mergeSort = (array,left,right)=>{
    const mid = Math.floor(left + (right - left) / 2)
    //进行拆分
    if(left < right){
        mergeSort(array,left,mid)
        mergeSort(array,mid+1,right)
        //进行合并
        merge(array,left,mid,right)
    }
}
const merge = (array,left,mid,right)=>{
    //创建一个新的数组
    const newArr = []
    //临时数组下标
    let c = 0
    let s = left
    //左右数组的开始位置
    let l = left
    let r = mid  + 1
    //来进行排序
    while(l <= mid && r <= right){
        //左子数组当前元素小的时候，说明此时没有逆序对
        if(array[l] <= array[r]){
            newArr[c] = array[l]
            l++
            c++
        }else{
            newArr[c] = array[r]
            count += mid+1 - l
            count %= 1000000007;
            r++
            c++
        }
    }
    //如果做子数组还有元素时，放入到临时数组里面
    while(l <= mid){
        newArr[c++] = array[l++]
    }
    while(r <= right){
        newArr[c++] = array[r++]
    }
    //将临时的数组中的元素放到原数组的指定位置
    for(let i = 0;i < newArr.length;i++){
        array[s++] = newArr[i]
    }


}