So implementieren Sie die Array-Merge-Sortierung und zählen die Anzahl der Paare in umgekehrter Reihenfolge in PHP (Code)

Der Inhalt dieses Artikels befasst sich mit der Implementierung der Array-Zusammenführungssortierung und der Berechnung der Anzahl der Paare in umgekehrter Reihenfolge (Code). Ich hoffe, dass er hilfreich ist Dir zu helfen.

Zwei Zahlen im Array. Wenn die erste Zahl größer als die zweite Zahl ist, bilden die beiden Zahlen ein Paar in umgekehrter Reihenfolge. Geben Sie ein Array ein und ermitteln Sie die Gesamtzahl der Paare P in umgekehrter Reihenfolge im Array. Und geben Sie das Ergebnis von P modulo 1000000007 aus. Das heißt, geben Sie P%1000000007 aus
1. Sortieren Sie das Array zusammen ist schlechter als der rechte Heap. Der erste ist der größte, dann ist er größer als alles im rechten Heap

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]

Das temporäre Array wird zurück in das ursprüngliche Array kopiert

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);

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Array-Merge-Sortierung und zählen die Anzahl der Paare in umgekehrter Reihenfolge in PHP (Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!