go語(yǔ)言題解LeetCode453最小操作次數(shù)使數(shù)組元素相等
題目描述
原題鏈接 :
453. 最小操作次數(shù)使數(shù)組元素相等 - 力扣（LeetCode） (leetcode-cn.com)
給你一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組，每次操作將會(huì)使 n - 1 個(gè)元素增加 1 。返回讓數(shù)組所有元素相等的最小操作次數(shù)。
示例 1：
輸入：nums = [1,2,3] 輸出：3 解釋： 只需要3次操作（注意每次操作會(huì)增加兩個(gè)元素的值）： [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
示例 2：
輸入：nums = [1,1,1] 輸出：0
提示：
n == nums.length
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
答案保證符合 32-bit 整數(shù)
思路分析
首先換個(gè)角度理解題目，將數(shù)組按順序表示為高度為nums[i]寬度為1的柱子，每次移動(dòng)i的含義為除i外的所有柱子高度加1，這樣i柱子與其他柱子的相對(duì)高度減1，可將移動(dòng)i理解為將i柱子高度減1，其他柱子不變。于是題目變?yōu)?，求將所有柱子減少為高度相等的柱子所需移動(dòng)次數(shù)。由于每次都只能減少某根柱子的高度1，所以最少要移動(dòng)sum(nums[i]-min(nums))次。
在遍歷nums的過程中，如果nums[i]大于之前的最小值，則nums[i]-min為需要減少的高度；
如果nums[i]小于之前的最小值，則需把前面沒有減少的高度i*(min-nums[i])，一次減掉。
AC 代碼
func minMoves(nums []int) int {
min := 1<<31 - 1
sum := 0
for i := range nums {
if nums[i] >= min {
sum += (nums[i]-min)
} else {
sum += i * (min-nums[i])
min = nums[i]
}
}
return sum
}
小結(jié)
這道題主要理解題意之后，轉(zhuǎn)換一下就簡(jiǎn)單了。
只需遍歷數(shù)組一次即可 - 最小操作次數(shù)使數(shù)組元素相等
遍歷數(shù)組一次
解題思路
對(duì)于要使得數(shù)組所有元素相等這個(gè)最終目標(biāo)而言，將n-1個(gè)元素加一其實(shí)等價(jià)于將剩下的那個(gè)元素減一，因此只需要將所有元素進(jìn)行減一操作直到等于數(shù)組中最小元素即可。所以最終的答案就是所有元素與最小元素的差值之和。
代碼
class Solution {
public int minMoves(int[] nums) {
if (nums.length<=1)
return 0;
int sum=0,min=Integer.MAX_VALUE;
int base = nums[0];
for (int num:nums){
sum+=num-base;
min=Integer.min(min,num);
}
return sum+(base-min)*nums.length;
}
}
強(qiáng)行找規(guī)律
解題思路
等于排序數(shù)組除第一位以外的和減去數(shù)組長(zhǎng)度減1乘以數(shù)組第一個(gè)數(shù)
代碼
class Solution:
def minMoves(self, nums: List[int]) -> int:
nums.sort()
return sum(nums[1:])-(len(nums)-1)*nums[0]
以上就是go語(yǔ)言題解LeetCode453最小操作次數(shù)使數(shù)組元素相等的詳細(xì)內(nèi)容，更多關(guān)于go最小操作數(shù)組元素相等的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
GoFrame?gmap遍歷hashmap?listmap?treemap使用技巧
這篇文章主要為大家介紹了GoFrame?gmap遍歷hashmap?listmap?treemap使用技巧的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-06-06
觀察者是一種行為設(shè)計(jì)模式， 允許一個(gè)對(duì)象將其狀態(tài)的改變通知其他對(duì)象，觀察者模式提供了一種作用于任何實(shí)現(xiàn)了訂閱者接口的對(duì)象的機(jī)制， 可對(duì)其事件進(jìn)行訂閱和取消訂閱，本文就通過代碼示例給大家詳細(xì)介紹一下Go的觀察者模式,需要的朋友可以參考下2023-07-07
Go 并發(fā)編程Goroutine的實(shí)現(xiàn)示例
Go語(yǔ)言中的并發(fā)編程主要通過Goroutine和Channel來實(shí)現(xiàn),本文就來介紹一下Go 并發(fā)編程的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-12-12
利用Go語(yǔ)言實(shí)現(xiàn)在終端繪制小兔子
這篇文章主要為大家詳細(xì)介紹了如何利用Go語(yǔ)言實(shí)現(xiàn)在終端繪制小兔子來給大家拜個(gè)早年，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2023-01-01
Golang中context庫(kù)的高級(jí)應(yīng)用
context庫(kù)不僅對(duì)于提升代碼的效率和性能至關(guān)重要,而且還幫助開發(fā)者在復(fù)雜的系統(tǒng)中保持代碼的清晰和可維護(hù)性,下面我們就來看看context庫(kù)的高級(jí)應(yīng)用吧2024-01-01
Go?Excelize?API源碼閱讀Close及NewSheet方法示例解析
這篇文章主要為大家介紹了Go?Excelize?API源碼閱讀Close及NewSheet方法示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-08-08
這篇文章介紹了Go語(yǔ)言通道之緩沖通道，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-07-07
在go語(yǔ)言中，要比較兩個(gè)對(duì)象是否完全相同，我們可以使用三種方法，這篇文章主要為大家介紹了這三種方法的具體實(shí)現(xiàn)，需要的可以參考一下2023-06-06
Go語(yǔ)言實(shí)現(xiàn)JSON解析的方法詳解
在日常項(xiàng)目中，使用Json格式進(jìn)行數(shù)據(jù)封裝是比較常見的操作。本文將詳細(xì)講解如何利用Go語(yǔ)言實(shí)現(xiàn)JSON的解析，感興趣的小伙伴可以學(xué)習(xí)一下2022-04-04
深入解析Go語(yǔ)言編程中slice切片結(jié)構(gòu)
這篇文章主要介紹了Go語(yǔ)言編程中slice切片結(jié)構(gòu),其中Append方法的用法介紹較為詳細(xì),需要的朋友可以參考下2015-10-10