LeetCode-Minimum Moves to Equal Array Elements

xiaoxiao2022-06-11  87

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]

题意:给定一个数组,计算最少经过多少次的移动可以使数组所有元素相等;每一次的移动都会令数组中n-1个元素增1;

解法:我们先定义如下变量:

数组移动前的和:sum数组的长度:n最少移动的次数:t移动后所有的元素均相等,每个元素都等于:x数组移动前的最小值:min

我们知道对于min来说,不管移动多少次,他都一直是最小值,因为其他元素也会增加,那么移动m次后,可以得到:

t + m i n = x t + min = x t+min=x

移动t次后,最后得到所有元素的和为t * x;对于移动前来说,增加了t*(n-1),可以得到: s u m + t ∗ ( n − 1 ) = t ∗ x sum + t*(n-1) = t*x sum+t(n1)=tx 由以上两个公式可以得到: t = s u m − m i n ∗ n t = sum - min*n t=summinn

Java
class Solution { public int minMoves(int[] nums) { int minNum = nums[0]; int sum = 0; for (int num : nums) { minNum = Math.min(minNum, num); sum += num; } return sum - minNum * nums.length; } }
转载请注明原文地址: https://www.6miu.com/read-4931434.html

最新回复(0)