关关的刷题日记82 – Leetcode 453. Minimum Moves to Equal Array Elements- 专知

关关的刷题日记82 – Leetcode 453. Minimum Moves to Equal Array Elements

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记82 – Leetcode 453. 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，就相当于每次使数组中的一个数减1：先找到数组中最小的数字，然后遍历数组所有元素，每个数与最小数字差值之和即为所求。

class Solution {
public:
    int minMoves(vector<int>& nums) {
        int minimum=INT_MAX, re=0;
        for(int x:nums)
            minimum=min(x,minimum);
        for(int x:nums)
            re+=x-minimum;
        return re;
    }
};