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

<?php

/*
- 题目：[BM20 数组中的逆序对](https://www.nowcoder.com/share/jump/4163484761690943983774)
- 实现：
    - 先把数组分隔成子数组 
    - 先统计出子数组内部的逆序对的数目
    - 然后再统计出两个相邻子数组之间的逆序对的数目
- 时间复杂度: O(nlogn)
- 空间复杂度: O(n)



- 题目要求
    - 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P
    - 题目保证输入的数组中没有的相同的数字
    - 要求：空间复杂度 O(n)，时间复杂度 O(nlogn)O
    - 并将P对1000000007取模的结果输出。 即输出P mod 1000000007
- 思路
    - 归并排序：分治的思想，这个过程需要使用递归来实现
    - 分：数组拆分
    - 治：每个小数组如何处理
*/


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

function mergeSort($arr, &$count)
{
    // 分：分到元素个数为1
    $size = count($arr);
    if($size <= 1) {
        return $arr;
    }

    // 再次拆分
    $mid = $size >> 1;
    $leftArr = array_slice($arr, 0, $mid);
    $rightArr= array_slice($arr, $mid);

    // 继续递归
    $left  = mergeSort($leftArr,$count);
    $right = mergeSort($rightArr,$count);

    // 合并
    return merge($left, $right, $count);
}

// 在合并两个已排序子数组的过程中统计逆序对的数量
function merge($leftArr, $rightArr, &$count) {
    $result = [];
    $leftSize = count($leftArr);
    $rightSize = count($rightArr);
    $i = 0;
    $j = 0;
    // 合并两个数组
    while($i < $leftSize && $j < $rightSize) {
        if($leftArr[$i] <= $rightArr[$j]) {
            $result[] = $leftArr[$i];
            $i++;
        } else {
            $result[] = $rightArr[$j];
            $j++;
            // 左边比右边大，答案增加
            // 如果是右边的数字更小，那么就是逆序对
            $count += count($leftArr) - $i;
        }
    }

    // 剩余的元素

    // 左侧的数组
    while ($i < $leftSize) {
        $result[] = $leftArr[$i];
        $i++;
    }

    // 右侧的数组
    while ($j < $rightSize) {
        $result[] = $rightArr[$j];
        $j++;
    }

    return $result;
}

$nums = [1,2,3,4,5,6,7,0];
var_dump(InversePairs($nums));

$nums = [364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575];
var_dump(InversePairs($nums));