【LeetCode通关全记录】453. 最小操作次数使数组元素相等
题目地址:453. 最小操作次数使数组元素相等
解法:求所有元素与数组最小元素之间的差值
这道题与其说是算法,不如说是考察逆向思维的脑筋急转弯吧。。。
其实思路很简单:每次操作使n - 1
个元素增加1,那么效果其实就相当于让数组中最大的数减1,所以只要先求出数组中的最小值,再求所有元素与这个最小值的差,最后把这些差都加起来就是我们需要的答案了。
如果不明白的话可以看官方题解,讲得很清楚。
func minMoves(nums []int) int {
min := nums[0]
// 找出数组中的最小值
for _, v := range nums {
if v < min {
min = v
}
}
// 计算数组中所有元素与数组最小值的差值
ans := 0
for _, v := range nums {
ans += v - min
}
return ans
}
执行用时: 32 ms(超过93.58%的Golang提交记录)
内存消耗: 6.6 MB(超过90.83%的Golang提交记录)
时间复杂度:O(n),需要一次遍历求出数组中的最小值,还需要一次遍历求出数组中的值与最小值的差;
空间复杂度:O(1),只使用了常数个数的存储空间。