[PHP] 算法-数组归并排序并计算逆序对的个数的PHP实现
2023-02-18 15:47:20 时间
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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);
相关文章
- 学习ASP.NET Core Razor 编程系列十二——在页面中增加校验
- 学习ASP.NET Core Razor 编程系列七——修改列表页面
- 学习ASP.NET Core Razor 编程系列五——Asp.Net Core Razor新建模板页面
- 学习ASP.NET Core Razor 编程系列四——Asp.Net Core Razor列表模板页面
- 学习ASP.NET Core Razor 编程系列三——创建数据表及创建项目基本页面
- YOLOAir:集成多种YOLO改进模块,面向小白科研的YOLO检测代码库
- Texturify:基于 GAN在 3D 形状表面上生成高质量纹理! 论文速递2022.8.30!
- [android] 切换界面的问题
- [android] 切换界面的通用处理
- [android] 界面切换的简单动画
- [android] 界面切换的核心方法
- [android] 界面的划分
- [javaSE] 面向对象(Object类toString)
- [javaSE] GUI(图形用户界面)
- [android] 新闻客户端主界面部分
- [android] 手机卫士界面切换动画
- [android] 手机卫士设置向导页面
- [android] 手机卫士欢迎细节和主界面
- 数仓是如何与“夏令时”愉快的玩耍?
- JVM面试必问:G1垃圾回收器