???? 算法题 ???? |
---|
???? 算法题 ???? |
---|
给你一个长度为n
的整数数组,每次操作将会使 n - 1
个元素增加1
。返回让数组所有元素相等的最小操作次数。
示例:
输入:nums = [1,2,3]
输出:3
解释:
只需要3次操作(注意每次操作会增加两个元素的值):
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
示例 2:
输入:nums = [1,1,1]
输出:0
提示:
使用return nums.Sum() - nums.Min() * nums.Length;
就可以搞定,但是Sum会溢出
所以修改为以下代码,遍历一遍即可!
代码:
public class Solution {
public int MinMoves(int[] nums) {
int iSum = nums.Min() * nums.Length * -1;
foreach (var num in nums)
{
iSum += num;
}
return iSum;
}
}
执行结果
通过
执行用时:156 ms,在所有 C# 提交中击败了53.85%用户
内存消耗:48.1 MB,在所有 C# 提交中击败了23.08%的用户
思路解析
代码:
public class Solution {
public int minMoves(int[] nums) {
int min = 0, max = nums.length - 1, count = 0;
while (true) {
for (int i = 0; i < nums.length; i++) {
if (nums[max] < nums[i]) {
max = i;
}
if (nums[min] > nums[i]) {
min = i;
}
}
if (nums[max] == nums[min]) {
break;
}
for (int i = 0; i < nums.length; i++) {
if (i != max) {
nums[i]++;
}
}
count++;
}
return count;
}
}
执行结果
超时
复杂度分析
时间复杂度:O( n^2 k ),其中 n 为数组长度,k 为最大值和最小值的差。
空间复杂度:O( 1)
思路解析
代码:
public class Solution {
public int minMoves(int[] nums) {
Arrays.sort(nums);
int moves = 0;
for (int i = 1; i < nums.length; i++) {
int diff = (moves + nums[i]) - nums[i - 1];
nums[i] += moves;
moves += diff;
}
return moves;
}
}
执行结果
通过
执行用时:13 ms,在所有 Java 提交中击败了20.05%的用户
内存消耗:38.6 MB,在所有 Java 提交中击败了92.21%的用户
复杂度分析
时间复杂度:O( nlog(n) )
空间复杂度:O( 1)
C#
和 Java
两种编程语言进行解题