給定一個(gè)非空整數(shù)數(shù)組,找到使所有數(shù)組元素相等所需的最小移動(dòng)數(shù),其中每次移動(dòng)可將選定的一個(gè)元素加1或減1谴轮。 您可以假設(shè)數(shù)組的長度最多為10000朽寞。
輸入:
[1,2,3]
輸出:
2
說明:
只有兩個(gè)動(dòng)作是必要的(記得每一步僅可使其中一個(gè)元素加1或減1):
[1,2,3] => [2,2,3] => [2,2,2]
解答:給數(shù)組排序识窿,后取index = n/2 的數(shù)據(jù)。所有的數(shù)朝它靠攏
func minMoves2(_ nums: [Int]) -> Int {
var inNums = nums;
inNums.sort()
let index = inNums.count / 2
let midNum = inNums[index]
var count = 0
for value in inNums {
count += abs(value - midNum)
}
return count
}
算法分析:目標(biāo)是最少移動(dòng)次數(shù)脑融。默認(rèn)數(shù)組已經(jīng)排好序
我們將數(shù)組數(shù)據(jù)分為left堆和right堆喻频。將數(shù)組最左與最右的兩個(gè)數(shù)據(jù)加入堆中。然后每次選擇一個(gè)堆肘迎,從剩余數(shù)據(jù)的左或右取出數(shù)據(jù)放入對應(yīng)堆中(這個(gè)堆的數(shù)據(jù)向另一邊靠攏)甥温。可以看出為了移動(dòng)次數(shù)最小每次都會(huì)選擇left妓布、right中數(shù)據(jù)較少的堆姻蚓,它朝另一個(gè)堆的方向移動(dòng)。當(dāng)任意一個(gè)堆取出index為n/2的數(shù)據(jù)時(shí)秋茫,它肯定成為數(shù)據(jù)最多的堆。于是可以認(rèn)定:所有的數(shù)據(jù)都朝index為n/2的數(shù)據(jù)靠攏時(shí)乃秀,移動(dòng)次數(shù)最小肛著。