D107 453. Minimum Moves to Equal Array Elements

题目链接

453. Minimum Moves to Equal Array Elements

题目分析

给定一个数组，对数组中的N-1个数组每次加1，返回最少需要多少步才能使得所有元素值相等。

思路

先想到的思路是，每一步都挑最小的n-1个元素去加。但很明显，每一步都排序排除最大的数字，再逐个相加，重新排序…是很耗时间的。因此我么要找到规律，简化求出所需步骤数的方法。

我们先分析简单点的，再推广。

1.1.1的情况下，直接返回即可。因为所有元素都是一样的。
1.1.2的情况下，只需一步即能变成2.2.2。
1.2.2的情况下，第一步是1.3.2；第二步是2.3.3；第三步是3.4.3；第四步是4.4.4。

1.3.5，2.4.5，3.5.5，4.6.5，5.7.5，6.7.6，7.7.7。共6步。这里觉得挺奇怪的，最终是7。猜了一下规律是5+3-1，即除去最小值的和减最小值是最终值，步骤是我就猜是最终值减最小值。

然而步骤数并不符合这个规律。例如1.2.2的情况，最终为4，但步骤数并不等于3。

进一步分析了一下6步是怎么得出的。
3-1=2，5-1=4，2+4 = 6。诶？巧了？
但发现对1.2.2的情况并不符合。

1.3.3，2.4.3，3.4.4，4.5.4，5.5.5。也是4步！
3+3-1=5。不对啊，那先全部加起来，再减吧：3+3+1-1-1，但还凑不成4，那就再减1吧。一共减了3个1。难道就是元素个数个1？
于是开始写代码测试 所有元素之和减去n个最小值（n为数组长度）。

结果就通过了。

最终代码

<?php
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function minMoves($nums) {
        $min = min($nums);
        return array_sum($nums) - count($nums) * $min;
    }
}

这代码居然只打败了60%！
我想…该不会是又min，又array_sum，又count导致的吧…
于是改成：

<?php
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function minMoves($nums) {
        $min = 9999999999999999999;
        $total = 0;
        $amount = 0;
        foreach($nums as $n){
            if($n<$min){
                $min = $n;
            }
            $total += $n;
            $amount++;
        }
        return $total - $amount * $min;
    }
}

就超过了80%的代码！
虽然也不是百分之百，不过也算是提高了点效率吧？

若觉得本文章对你有用，欢迎用爱发电资助。