数组中的逆序对

未匹配的标注

题目描述

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

输入描述:题目保证输入的数组中没有的相同的数字

数据范围:对于%50的数据,size<=10^4。对于%75的数据,size<=10^5。对于%100的数据,size<=2*10^5

输入:

1,2,3,4,5,6,7,0

输出:

7

分析

题目的意思就是求每个元素后面有多少个数比它小,全部加起来就是逆序对的总数。使用归并排序来解。
例子:8,5,7,2

  1. 将数组分到最后只剩一个元素,如图最后一层所示。

    Uhy8HWQL4M.png!large
  2. 8 5合并成5 8,同理,7 2合并成2 7
    合并过程中,如果右边数组值小于左边数组值,则产生逆序对。产生的逆序对个数等于左边数组的个数。

    kEEDbJ96Ep.png!large
  3. 5 8 2 7合并成2 5 7 8
    合并过程中,产生3个逆序对。

    Pt1zb2Qw30.png!large

代码

<?php

namespace app\index\controller;

class Test extends TestCase
{
    // 测试
    public function test()
    {
        $data = [8, 5, 7, 2];
        $res = $this->InversePairs($data);
        echo $res;
    }


    /**
     * 传递原数组的引用,会修改到数组,最终是排好序的数组
     */
    function InversePairs(&$data)
    {
        if (count($data) < 2) return 0;
        $res = $this->comparator($data, 0, count($data) - 1);  // 调用
        return $res;
    }


    /**
     * 递归分数组
     */
    function comparator(&$data, $left, $right)
    {
        if ($left == $right) return 0;              // 如果分到最后剩一个元素,则直接返回
        $mid = floor($left + ($right - $left) / 2); // 将数组分成两部分

        $leftPairs  = $this->comparator($data, $left, $mid);       // 继续分左边
        $rightPairs = $this->comparator($data, $mid + 1, $right);  // 继续分右边
        $crossPairs = $this->merge($data, $left, $mid, $right);    // 将左边和右边合并起来

        return $leftPairs + $rightPairs + $crossPairs;  // 逆序对 = 左边个数+右边个数+合并个数
    }


    /**
     * 合并数组
     */
    function merge(&$data, $left, $mid, $right)
    {
        $p1    = $left;      // 初始值:左边数组的第一个元素
        $p2    = $mid + 1;   // 初始值:右边数组的第一个元素
        $count = 0;          // 逆序对总数
        $help  = [];         // 辅助数组

        while ($p1 <= $mid && $p2 <= $right) {
            // 如果左边值 <= 右边值,则放左边值到辅助数组
            if ($data[$p1] <= $data[$p2]) {
                $help[] = $data[$p1++];
            } else {
                // 否则,放右边值到辅助数组,并计算逆序个数。$mid-$p1+1是左数组的个数
                $count = $count + ($mid - $p1 + 1);
                $help[] = $data[$p2++];
            }
        }

        while ($p1 <= $mid) {  // 右数组走完了,剩左数组,直接放入辅助数组
            $help[] = $data[$p1++];
        }
        while ($p2 <= $right) { // 左数组走完了,剩右数组,直接放入辅助数组
            $help[] = $data[$p2++];
        }

        // 将辅助数组放回原数组
        for ($i = 0, $len = count($help); $i < $len; $i++) {
            $data[$left + $i] = $help[$i];
        }
        return $count;
    }
}

本文章首发在 LearnKu.com 网站上。

上一篇 下一篇
讨论数量: 0
发起讨论 查看所有版本


暂无话题~