[Leetcode 453] Minimum Moves to Equal Array Elements

作者 Shilei Tian 日期 2016-12-27
[Leetcode 453] Minimum Moves to Equal Array Elements

题目要求

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]

解题思路

这道题乍一看还真是一点思路都没有…然后就点了 Top Solutions 看到了其中的一个写的是 Math Problem,原来如此。

什么叫数学问题 呢?就是可以用数学公式来解决的问题,这道题目就是这个样子。我们定义原序列的sum,那么进行一次 move 的话,对序列的产生的影响就是 sum_new = sum + n - 1。假设我们需要 m 次,那么最终得到的和则是 sum_final = sum + m * (n - 1)。我们还有一个性质没有用,就是最终序列每个元素都是相同的,我们假设它是 x,则有 sum_final = x * n,那我们就可以得到一个等式:sum + m * (n - 1) = x * n,相应地,我们得到了 m 的表达式为 m = (x * n - sum) / (n - 1)

有了 m 的表达式,但是我们并不能解它,因为这里面 x 的值我们不知道。我们定义原序列中最小的元素为 a,那么我说 x = a + m,也就是每一步的 move 都会作用在这个最小的元素。这是为什么呢?我们用反证法来证明它。假设 a_final = a + k,就是说我们只将 k 次作用在最小的元素上,k < m。任选另外一个元素 bb > a 肯定成立,而 b 的最终情况分为 3 种:

  1. 每次作用在 a 上的同时也作用b 上,剩下那 m - k 次我们不需要考虑,那么 b_final >= b + k。由于最终各个元素相同,则我们有 b_final = a + k >= b + k,显然不成立。
  2. 每次作用在 a 上的同时都不作用在 b 上,那么我们可以得出结论,对于其他的任何元素 c,每一次 move 都作用在 c 上。这样 a_final = a + kc_final = c + m,并且 a + k = c + k。但是由于 a 是最小的元素,因此上式肯定不成立。
  3. 作用在 a 上的 move,有时候作用在 b 上,有时候不作用在 b 上。假设我们有 l 次作用在了 b 上,那么我们从剩下元素中任取一个 c,使得 a < c < b,那么我们它至少增加了 m - k + k - l 次,即 m - l次,那么 c_final >= c + m - l。我们还能够得到 a_final = a + kb_final = b + l + m - k,并且 a_final = b_final = c_final。(但是剩下部分推不出来…等想出来了再补充)

因此,有了 x 和最小值之间的关系,我们就可以得到 m = sum - a * n,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int minMoves(vector<int>& nums) {
int sum = accumulate(nums);
int minVal = min(nums);
return sum - minVal * nums.size();
}

private:
int min(vector<int>& nums) {
int min = nums[0];
for (auto num : nums) {
if (num < min) {
min = num;
}
}
return min;
}
int accumulate(vector<int>& nums) {
int sum = 0;
for (auto num : nums) {
sum += num;
}
return sum;
}
};