LeetCode之路：453. Minimum Moves to Equal Array Elements

一、引言

这是一道让人看上去有些困扰的题目，而本人也确实花了不少的时间，钻入了自己的思维陷阱里面，后面又出现了不少的编译问题，扰乱了自己的解题思绪。最后的最后，当看到了最高票答案之后，才发现：

It’s a math question.

现在感慨良多 T_T，让我们先来看看这道题目吧：

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

题目信息较少，这里简单翻译下：

给定一个元素数量为 n 的非空数组，请找到这么一个最小的移动数字使这个数组的所有元素相等，其中，一次移动意味着将 n - 1 个元素加 1。

举例：
输入：
[1, 2, 3]
输出：
3
解释：只需要三次移动操作（每次移动增加两个元素）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

这里需要详细解释下这道题的意思：

1. 首先，我们需要注意的是我们的目的，是要使给定数组的所有元素相等，其中，我们只能使用一个操作来使得数组的所有元素相等，那就是 n - 1 个元素加 1

2. 其次，我们要了解什么叫做 n - 1 个元素加 1，比如我们看看那个例子：

   [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

   我们收到了 [1, 2, 3] 的参数数组，我们看到了最大元素值为 3，那么我们的首次肯定选择最大值不动，其他 n - 1 个元素加 1；然后我们看到了 [2, 3, 3]，于是我们继续将最大值不动其他 n - 1 个元素值加 1；现在我们看到了 [3, 4, 3]，同样的，我们将最大值不动其他数值加 1 得到 [4, 4, 4]，至此过程结束

3. 最后，我们还需要记住的是，数组元素非空，意味着我们可以取任意值，比如 [-2147483648,-2147483647] 或者 [1,2147483647] 这种 case 也是可以的

这里分析的过程中，其实已经暴露了我的思维过程了，我的首入思维并不是使用数学方法，而是使用编程设计去模拟我们移动的过程。

二、Runtime Error：模拟自己的移动过程

为什么给这个标题起名为 Runtime Error 呢？

因为在这个思路下，我遇到了太多的 Runtime Error 了，并且也因为最后的一个方法 Submit 后得到了 Runtimer Error 之后，终于悬崖勒马。

不过，这个思路虽然我的尝试并没有成功，但是这种使用编程设计来模拟自己的移动过程的过程，也是一种非常有趣的体验（^_^有兴趣的同学可以看看这里，没兴趣的可以直接看第三个标题寻找这道题的正确答案）。

那么我的思路是什么呢：

1. 首先：我们拿到了一个数组

2. 其次：我们寻找它的第一个最大值（可能有多个相同的最大值），我们将第一个最大值之外的所有元素全部加 1

3. 最后：我们判断数组的元素是否全部相当，不相等的话继续第 1、2 步

这个思路是一个典型的递归的思想，那么代码就出来了：

// my solution 1 , Compile Error
class Solution {
public:
    int minMoves(vector<int>& nums) {
        auto min = min_element(nums.begin(), nums.end());
        auto max = max_element(nums.begin(), nums.end());
        if (*min == *max) return count;
        for (int i = 0; i < nums.size(); ++i) {
            if (max - nums.begin() != i) ++nums[i];
        }
        ++count;
        return minMoves(nums);
    }

private:
    int count = 0;
};

简单说下代码：

1. 首先，我使用了 std::min_element 和 std::max_element 标准库函数获取了数组中的最大值和最小值，判断是否相等，如果相等的话就可以直接返回了

2. 然后，我根据 std::max_element 返回的迭代器定位了第一个最大值的位置，于是乎遍历了整个数组，将除了第一个最大值之外的所有元素值加 1

3. 最后，递增计数，递归调用本函数

但是这个方法并没有通过所有的 case，我猜测是因为 Test Case 中含有太过于庞大的数字，导致运行（尤其是递归）占用空间太大，于是 Complie Error 了 。

可是看到了 Compile Error 的我并不准备认输，因为我小小思考了下，这个方法仍然有着可优化点！

比如说我们给出这么一个 Case:

[1, 2147483647]

按照我们上面的方法来运行，明明一个减法就能得到答案的数组，我们却要递归 2147483647 - 1 次。

根据这个思考，我拿出了第二最大值的概念：

试想一下，我们在递归运算前将数组中的最大值和第二最大值进行差值运算，然后将第二最大值手动加到第一最大值的值，在只有达到了第一最大值和第二最大值的相等后才进行递归运算，这样就可以减少不少的递归运算了

根据这个思想的指导，我写出了以下的代码：

class Solution3 {
public:
    int minMoves(vector<int>& nums) {
        auto max = max_element(nums.begin(), nums.end());
        auto min = min_element(nums.begin(), nums.end());
        if (*max == *min) return count;
        int maxTemp = *max;
        *max = INT_MIN;
        auto max_second = max_element(nums.begin(), nums.end());
        *max = maxTemp;
        int distance = *max - *max_second == 0 ? 1 : *max - *max_second;
        count += distance;
        for (int i = 0; i < nums.size(); ++i) {
            if (max - nums.begin() != i) nums[i] += distance;
        }
        return minMoves(nums);
    }

private:
    int count = 0;
};

代码逻辑非常清晰，找最大值、最小值进行比较，然后找第二最大值直接加到第一最大值后进行递归调用。

但是这个方法也失败了 T_T ~~~

Runtime Error, Error Case:
[83,-14,77,15,93,35,86,-8,-51,-79,62,-73,-10,-41,63,26,40,-74,72,36,-89,68,67,-71,82,30,-38,23,-33,35,29,-98,-78,-42…

看到了这里，我终于明白了，这条路是走不通的 : (

因为数组的元素太多，数值相差有可能非常巨大，LeetCode 根本没有给你能够使用这个方法递归出来的编译空间，所以当递归占用了所有的空间之后， Runtime Error 了 ~~~

看来，这条路算是死心了，谁能告诉我，这道题的出路是哪里？

三、It’s a math question：数学又来拯救世界了

最高票答案如是曰：

It’s a math question.

这里我放了张截图，英语好的同学应该能够很容易的读懂，这里我还是简单翻译下：

让我们定义 sum 为移动前数组中所有元素的和； minNum 为数组中最小的元素值； n 是数组的长度
那么，在 m 次移动操作后，我们得到了数组的元素为 x （此时数组中的元素已经全部相等），于是我们可以得到这么一个关系：
sum + m * (n - 1) = x * n
实际上：
x = minNum + m
最后，我们能够得到这么一个关系式：
sum - minNum * n = m
所以现在这个问题非常简单了

这里还是简要解释下，可能有些同学还是没有清楚：

1. 首先，我们需要明白，数组的最后状态肯定是所有元素相等，我们拿着这个相等的元素值 x，就可以得到这么一个关系式：

   sum + m * (n - 1) = x * n

   这个式子是什么意思呢？sum 也就是所有元素的和，x * n 也就是移动操作后所有元素的和；m 是我们的移动次数，因为我们每次操作都是将 n - 1 个元素的值加 1，因此每次移动操作都实际上给所有元素的和增加了 n - 1 的增量值；因此我们得到了上述这个等式

2. 然后，我们还找到了这么一个式子：

   x = minNum + m

   这个式子又是什么意思呢？x 是移动后的元素值，minNum 是移动前数组中最小的值，那么我们通过了移动操作使得 minNum 变成了 x，你说 x 等不等于 minNum + m 呢 ^_^

3. 最后，我们将这两个式子结合起来，得到了这么一个式子：

   sum - minNum * n = m

   这个式子中，sum 可得，minNum 可得，n 已知，m （也就是移动此时）就可以求出来了

代码如下：

// perfect solution , runtime = 52 ms
class Solution4 {
public:
    int minMoves(vector<int>& nums) {
        int sum = 0, moves = 0;
        auto minIt = min_element(nums.begin(), nums.end());
        for (auto i : nums) sum += i;
        return sum - *minIt * nums.size();
    }
};

代码也就是照着 sum - minNum * n = m 的公式来写的，就不再赘述了。

另外，我们将公式转型下：

(nums[i] - minNum) * n = m

其中 nums[i] 为移动前数组中的各个元素，那么我们只需要遍历计算差值就可以了：

// another perfect solution , runtime = 53 ms
class Solution5 {
public:
    int minMoves(vector<int>& nums) {
        int moves = 0;
        auto minIt = min_element(nums.begin(), nums.end());
        for (auto i : nums) moves += i - *minIt;
        return moves;
    }
};

至此，我们终于算是简洁、优雅地做完了这道题。

四、总结

就像最高票答案写的那样：

It’s a math question.

有时候设计的时候多思考一些，编写程序的时候就能省下好多时间，并且也能节省不少的时间、空间占用率。

不过，我认为解决问题的过程本来就是一种快乐的探索过程，有些答案至上的人可能觉得我第二个部分写的又繁琐又没有意义，但是我觉得，这反而是这道题带给我最大的收获：

面对一个问题，自己思考一个思路，然后穷尽自己的能力去实现这个思路；在实现自己的思路的路上，难免会遇到这样那样的问题，于是去思考解决办法，要么穷尽所思，要么更换思路；尽管走到了一条死路，但这不值得惭愧；探索本身就是一种成长。

最近的工作涉及到的逻辑问题比较复杂，加之这道题探索得比较久，做题的速度有所下降。不过没什么，速度不代表质量，我仍然斥尽自己的能力去面对每一道 LeetCode 上的题目 ： )

To be Stronger!