小和问题.md

小和问题

什么是小和问题

在一个数组中, 每一个数左边比当前数小和数累加起来, 叫做这个数组的小和, 求一个数组的小和

例如:
[1, 3, 4, 2, 5]
1左边比1小的数, 没有
3左边比3小的数, 1
4左边比4小的数, 1、3
2左边比2小的数, 1
5左边比5小的数, 1、3、4、2
所以小和 = 1 + (1 + 3) + 1 + (1 + 3 + 4 + 2)

代码

最简单的办法: 遍历

<?php

function smallSum($arr)
{
    $sum = 0;

    // 从第二个元素开始
    for ($i = 1; $i < count($arr); $i++) {
        for ($j = $i - 1; $j >= 0; $j--) {
            if ($arr[$j] < $arr[$i]) {
                $sum += $arr[$j];
            }
        }
    }

    return $sum;
}

// Test
$arr = [1, 3, 4, 2, 5];
// 16
var_dump(smallSum($arr));

使用归并排序的思路进行优化

<?php

class SmallSum
{

    public static function sort(&$arr, $left, $right)
    {
        if ($left == $right) {
            return 0;
        }

        $mid = floor(($left + $right) / 2);

        return self::sort($arr, $left, $mid) + self::sort($arr, $mid + 1, $right) + self::merge($arr, $left, $mid, $right);
    }

    public static function merge(&$arr, $left, $mid, $right)
    {
        $res = 0;
        $p1 = $left;
        $p2 = $mid + 1;
        $help = [];

        while ($p1 <= $mid && $p2 <= $right) {
            $res += $arr[$p1] < $arr[$p2] ? ($right - $p2 + 1) * $arr[$p1] : 0;
            $help[] = $arr[$p1] < $arr[$p2] ? $arr[$p1++] : $arr[$p2++];
        }

        while ($p1 <= $mid) {
            $help[] = $arr[$p1++];
        }
        while ($p2 <= $right) {
            $help[] = $arr[$p2++];
        }

        for ($i = 0; $i < count($help); $i++) {
            $arr[$left + $i] = $help[$i];
        }

        return $res;
    }
}

// Test
$arr = [1, 3, 4, 2, 5];
// 16
var_dump(SmallSum::sort($arr, 0, count($arr) - 1));

优化的思路是?

            1 3 4 2 5
       1 3 4         2 5
    1 3     4       2   5
   1   3
优化的关键代码是:
$res += $arr[$p1] < $arr[$p2] ? ($right - $p2 + 1) * $arr[$p1] : 0;

左半部分的小和是 1 + (1+3)
右半部分的小和是 2
左半部分相对于右半部分的小和是 1*2 + 3*1 + 4*1