PHP で配列のマージ ソートを実装し、逆順ペアの数を数える方法 (コード)

この記事の内容は、PHP がどのように配列マージソートを実装し、逆順ペアの数を計算するか (コード) に関するものです。一定の参考値があります。必要な友人は参考にしてください。お役に立てば幸いです。手伝う。

配列内の 2 つの数値。前の数値が次の数値より大きい場合、2 つの数値は逆順のペアを形成します。配列を入力し、配列内の逆順ペアの総数 P を求めます。そして、P モジュロ 1000000007 の結果を出力します。つまり、出力 P 00000007
1. 配列のマージ ソート
2. マージ ソート 左ヒープ配列と右ヒープ配列の要素のサイズを比較する場合は、左ヒープが最初であるため、逆方向に数えて比較します。右ヒープよりも悪い 最初のヒープが最も大きく、次に右ヒープ内のすべてのヒープよりも大きくなります

mergeSort
    if left<right
        mid=[(p+r)/2]
        mergeSort(arr,left,mid,temp)
        mergeSort(arr,mid+1,right,temp)
        merge(arr,left,mid,right,temp)
merge(arr,left,mid,right,temp)
    i=mid
    j=right
    t=right
    while i<=mid && j<=right
        if arr[i<arr[j]
            temp[t--]=arr[i--]
        else
            count+=mid-i+1
            temp[t--]=arr[j--] 
    while i<=mid
        temp[t--]=arr[i]
    while j<=right
        temp[t--]=arr[j]

一時配列は元の配列にコピーされます

function InversePairs($data)
{
    $num=0;
    $temp=array();
    mergeSort($data,0,count($data)-1,$temp,$num);
    $num%=1000000007;
    return $num;
}
//1.利用分治法思想,递归的切分排序元素
function mergeSort(&$A,$left,$right,$temp,&$num){
        //2.最左只能小于最右,等于的时候就一个元素,大于是不可能的
        if($left<$right){
                //3.获取中间的元素
                $mid=intval(($left+$right)/2);
                //4.递归左半区
                mergeSort($A,$left,$mid,$temp,$num);
                //5.递归右半区
                mergeSort($A,$mid+1,$right,$temp,$num);
                //6.合并两个有序数组为一个有序数组
                merge($A,$left,$mid,$right,$temp,$num);
        }
}
function merge(&$A,$left,$mid,$right,$temp,&$num){
        //7.左堆起始
        $i=$left;
        //8.右堆起始
        $j=$mid+1;
        //9.临时数组起始
        $t=0;
        //10.左右堆数组都没到末尾
        while($i<=$mid && $j<=$right){
                //11.左堆小于等于右堆时
                if($A[$i]<$A[$j]){
                        //12.左堆赋给临时数组,索引加1
                        $temp[$t++]=$A[$i++];
                }else{

                        $num+=$mid-$i+1;
                        //13.右堆赋给临时数组,索引加1
                        $temp[$t++]=$A[$j++];
                }
        }
        //14.左堆剩余的全部加进临时数组
        while($i<=$mid){
                $temp[$t++]=$A[$i++];
        }
        //15.右堆剩余全部加进临时数组
        while($j<=$right){
                $temp[$t++]=$A[$j++];
        }
        //16.临时数组的元素重新赋回原数组
        for($i=0;$i<$t;$i++){
                $A[$left+$i]=$temp[$i];
        }
}
$A=[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,74
6,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,43
3,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575];

$m=InversePairs($A);

var_dump($m);

以上がPHP で配列のマージ ソートを実装し、逆順ペアの数を数える方法 (コード)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。