Problem
题目大意:给你一个数组,每次可以把其中n-1个数加1,问最少需要多少次操作可以使得数组中的元素都相等。
https://leetcode.com/problems/minimum-moves-to-equal-array-elements/description/
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]
Idea
Assuming the sum of array is S, the minimum element of the array is min and minimum number of moves is m.
Each move will increase the sum of array by n – 1. Finally, every element becomes x. So we have:
- S + (n – 1) * m = x * n
- min + m = x
We got: m = S – n * min
Solution: Math
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 |
// Author: Huahua // Running time: 51 ms class Solution { public: int minMoves(const vector<int>& a) { return accumulate(a.begin(), a.end(), 0L) - a.size() * *min_element(a.begin(), a.end()); } }; |
Python
1 2 3 4 5 6 7 |
""" Author: Huahua Running time: 104 ms """ class Solution: def minMoves(self, nums): return sum(nums) - len(nums) * min(nums) |