[LeetCode] 453. Minimum Moves to Equal Array Elements

轉自LeetCode

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]

<Solution>

這題要從反面思考一下

長度 n 的 array，每次 move 是 n-1 個 element 都加 1

這就代表，每次 move，是剩餘的那一個 element 減1

因此，只要知道每個 element 需要減一幾次，才會變成最小的數字

然後總合起來就是答案

最後的總和方式，四則運算分配一下，就變成  sum - min * length

例如 [1, 2, 3]

(1 - 1) + (2 - 1) + (3 - 1) = (1 + 2 + 3) - 1 * 3

	class Solution {
	public:
	int minMoves(vector<int>& nums) {
	int sum = 0;
	int minNum = 2147483647;
	//> calculate the sum and find the min value
	for(auto n : nums) {
	sum += n;
	if(n < minNum) {
	minNum = n;
	}
	}
	return (sum - minNum * nums.size());
	}
	};

view raw minMove.cpp hosted with ❤ by GitHub