Leetcode PHP题解--D107 453. Minimum Moves to Equal Array Elements


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.52.4.53.5.54.6.55.7.56.7.67.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.32.4.33.4.44.5.45.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%的代码!
虽然也不是百分之百,不过也算是提高了点效率吧?

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


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode刷题之PHP解析( 154. Find Minimum in Rotated Sorted Array II)

>> 下一篇: 基于 Nginx + ModSecurity 构建防火墙