跳转至

LeetCode: 453. 最小移动次数使数组元素相等

1、题目描述

给定一个长度为 n 的**非空**整数数组,找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。

示例:

输入:
[1,2,3]

输出:
3

解释:
只需要3次移动(注意每次移动会增加两个元素的值):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

2、解题思路

​ 理解题意很重要,实际上,上面的描述主要表达了一个问题,每一次选取n-1个元素,使他们增加1,其实对应着另外一层意思,就是每次选取一个元素,使它减一,也就是说,题目的需要是将所有的元素调整为相等的,也就是说计算所有的元素相对于最小元素的差值就可以了

int minMoves(int* nums, int numsSize) {
    int min = nums[0];
    int result = 0;

    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < min) {
            min = nums[i];
        }
    }

    for(int i = 0;i<numsSize;i++){
        result+= nums[i] - min;
    }

    return result;
}