QQ登录

只需一步,快速开始

新浪微博登陆

只需一步, 快速开始

切换风格 注册 找回密码

php开发-PHP教程网


发表于 2018-9-20 14:16:34 | 显示全部楼层 |阅读模式
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数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
    while j<=right
        temp[t--]=arr[j]
    临时数组重新复制回原数组



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

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

  58. $m=InversePairs($A);

  59. var_dump($m);
复制代码

发表于 2018-9-20 14:17:04 | 显示全部楼层
看起来不错
发表于 2018-9-20 23:19:39 | 显示全部楼层
顶起顶起顶起
发表于 2018-9-22 06:00:16 | 显示全部楼层
支持,赞一个
发表于 2018-9-22 18:08:22 | 显示全部楼层
无论是不是沙发都得回复下
发表于 2018-9-22 21:02:42 | 显示全部楼层
垃圾内容,路过为证。
发表于 2018-9-23 05:15:53 | 显示全部楼层
我也顶起出售广告位
发表于 2018-9-23 12:43:42 | 显示全部楼层
没人回帖。。。我来个吧

新浪微博达人勋

发表于 2018-9-23 14:44:45 | 显示全部楼层
看起来好像不错的样子
发表于 2018-9-24 03:43:17 | 显示全部楼层
支持,赞一个
您需要登录后才可以回帖 登录 | 立即注册 新浪微博登陆



Archiver|  

662p开源网. Powered by Niuzen

© 2001-2014 Niuzen Inc.

返回顶部