[PHP] 算法-数组归并排序并计算逆序对的个数的PHP实现
2023-02-18 15:41:47 时间
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 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);
相关文章
- 小细胞肺癌化疗耐药相关的肿瘤外显子层面差异
- MacOS怎么设置动态桌面,heic动态桌面壁纸怎么用
- 大芯片面临的共同挑战
- 软硬件融合:超异构计算革命(第七版,附下载链接)
- “黄金年代”之后,计算机体系结构将何去何从?
- 单细胞转录组计算肿瘤纯度应该是金标准吗?
- 什么是复杂计算?
- 在你的髓系里面加上中性粒吧
- 云服务器宝塔面板+Tomcat+LNMP部署JAVA WEB
- Java面试集锦(一)
- 【DevCloud · 敏捷智库】两种你必须了解的常见敏捷估算方法
- 技术干货丨通过wrap malloc定位C/C++的内存泄漏问题
- 一文带你了解Web前端发展历程
- 实战案例丨代码优化:如何去除context中的warning?
- 干货分享丨jvm系列:dump文件深度分析
- 成熟度模型:企业规模化推广敏捷和DevOps利器
- 毕业遇上疫情怎么办?4条技术指南轻松应对(内含求职、租房攻略)
- 云小课 | “VPC连接”知多少
- 华为云MVP熊保松谈物联网开发:华为云IoT是首选,小熊派是神器
- 过滤器 和 拦截器6个区别,别再傻傻分不清了