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)资助。