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
                                       <?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% 的代码！虽然也不是百分之百，不过也算是提高了点效率吧？若觉得本文章对你有用，欢迎用 [爱发电](https://afdian.net/@skys215) 资助。