未分類

Minimum Moves to Equal Array Elements

Go, LeetCode, Math

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.

For Example:

1
2
3
4
5
6
7
8
9
10
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]
提示 解題應用
Math 規律觀查

Default:

1
2
3
func minMoves(nums []int) int {
}

解答思路:

如果照題目的規則去想很容易就會卡很久，若給一長度n的數量，每次都要給n-1個數+1直到n個數的值都相同為止，找出最少需要多幾次，直接照這種方式來迴圈不斷判斷，每次都要先找出最大值之後再對其它數+1，很容易因為陣列長度極長，或元素值之間差異極大而花費過多的時間，再加上因為不曉得加到最後一樣數時會是多少，難以預測就很難不一步步慢慢增加，因此如果能反過來推想就會變的相當簡單，既然要給n-1個數+1，反過來推其實就是對1個數-1直到n個數都一樣小，而要變的一樣小其實就是陣列中的最小值，所以再找出最小值之後剩下的就只是將每個元素與最小值的差做相加就是結果了。

程式碼解說:

首先將陣列的第一個值取出，接下來再與陣列其它值一一比較，如果發現有更小的值就放入變數中，再找出最小值之後接著再進行最後一次遍歷，將每個元素與最小值的差做相加，最後再遍歷結束後回傳結果

1
2
3
4
5
6
7
8
9
10
11
var count int
min := nums[0]
for _, v := range nums[1:] {
	if v < min {
		min = v
	}
}
for _, v := range nums {
	count += v - min
}
return count

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
func minMoves(nums []int) int {
	var count int
	min := nums[0]
	for _, v := range nums[1:] {
		if v < min {
			min = v
		}
	}
	for _, v := range nums {
		count += v - min
	}
	return count
}

總結:

若給一長度n的數量，每次都要給n-1個數+1直到n個數的值都相同為止，找出最少需要多幾次，反過來推想其實就是對1個數-1直到n個數都一樣小，而要變的一樣小其實就是陣列中的最小值，所以再找出最小值之後再來只要將每個元素與最小值的差做相加就是結果。

分享到