Files
2020-08-12 20:12:33 +08:00

51 lines
1.5 KiB
Markdown
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

# [453. Minimum Moves to Equal Array Elements](https://leetcode.com/problems/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]
```
## 题目大意
给定一个长度为 n 的非空整数数组,找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。
## 解题思路
- 给定一个数组,要求输出让所有元素都相等的最小步数。每移动一步都会使得 n - 1 个元素 + 1 。
- 数学题。这道题正着思考会考虑到排序或者暴力的方法上去。反过来思考一下,使得每个元素都相同,意思让所有元素的差异变为 0 。每次移动的过程中,都有 n - 1 个元素 + 1那么没有 + 1 的那个元素和其他 n - 1 个元素相对差异就缩小了。所以这道题让所有元素都变为相等的最少步数,即等于让所有元素相对差异减少到最小的那个数。想到这里,此题就可以优雅的解出来了。
## 代码
```go
package leetcode
import "math"
func minMoves(nums []int) int {
sum, min, l := 0, math.MaxInt32, len(nums)
for _, v := range nums {
sum += v
if min > v {
min = v
}
}
return sum - min*l
}
```