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

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
 */
function InversePairs( $nums )
{
    $len = count($nums);
    if($len <= 1){
        return 0;
    }
    $count = 0;
    mergeSort($nums, 0, $len-1, $count);
    return $count % 1000000007;
}

function mergeSort(&$arr, $lower, $higher, &$count)
{   
    if($lower >= $higher){
        return;
    }
    $mid = intval(($lower+$higher)/2);
    mergeSort($arr, $lower, $mid, $count);
    mergeSort($arr, $mid+1, $higher, $count);
    merge($arr, $lower, $mid, $higher, $count);
}

function merge(&$arr, $lower, $mid, $higher, &$count){
    printf("low: ".$lower." high: ".$higher."\n");
    $tempArr = [];
    $c = 0;
    $l = $lower;
    $r = $mid+1;
    while($l <= $mid && $r <= $higher){
        if($arr[$l] < $arr[$r]){
            $tempArr[$c++] = $arr[$l++];
        }else{
            $tempArr[$c++] = $arr[$r++];
            $count += $mid-$l+1;
            printf("mid: ".$mid." l: ".$l);
        }
    }
    while($l <= $mid){
        $tempArr[$c++] = $arr[$l++];
    }
    while($r <= $higher){
        $tempArr[$c++] = $arr[$r++];
    }
    for($c=0, $i = $lower;$i <= $higher;$i++,$c++){
        $arr[$i] = $tempArr[$c];
    }
}

方法一：暴力解法O(nlogn)

方法二：归并法，类似归并排序。归并排序merge两个list时，如果左边的list当前值大于右边的当前值，证明左边（当前值-mid)全部大于右边的当前值，逆序对的数量+=（$mid-$l+1）

注意：逆序对的总数量用实参的方式累计，归并排序后的结果也要更新到原array上，两个都是实参传参