題目
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]
解題思路
審題是多么重要退子，每個(gè)操作是將n-1個(gè)元素加1，也就是讓另外一個(gè)元素減1.想到這里就簡單了瑰步，問題變成了累加數(shù)組中各元素與最小值之差
代碼
minMoves.go
package _453_Minimum_Moves2Equal_Array_Elements
func MinMoves(nums []int) int {
var min int
min = nums[0]
length := len(nums)
for i := 1; i < length; i++ {
if min > nums[i] {
min = nums[i]
}
}
if 1 == length {
return 0
}
var sum int
for i := 0; i < length; i++ {
sum += nums[i]
}
return sum - min * length
}
測(cè)試
minMoves_test.go
package _453_Minimum_Moves2Equal_Array_Elements
import "testing"
func TestMinMoves(t *testing.T) {
var tests = []struct{
input []int
output int
}{
{
[]int{1, 2, 3}, 3,
},
{
[]int{83,86,77,15,93,35,86,92,49,2}, 598,
},
}
for _, test := range tests {
ret := MinMoves(test.input)
if ret == test.output {
t.Logf("pass")
} else {
t.Errorf("fail, want %+v, get %d", test.output, ret)
}
}
}
