電梯在高峰時(shí)間抓督，每層都有人上下，電梯每層都停椿浓，在繁忙的上下班時(shí)間带斑，每次電梯從一層往上走時(shí)，假設(shè)只允許電梯停在其中的某一層晾匠。所有乘客從一樓上電梯，到達(dá)某層后，電梯停下來食磕，所有乘客再?gòu)倪@里爬樓梯到自己的目的層。在一樓的時(shí)候喳挑，每個(gè)乘客選擇自己的目的層彬伦，電梯則計(jì)算出應(yīng)停的樓層。
問：電梯停在哪一層樓伊诵，能夠保證這次乘坐電梯的所有乘客爬樓梯的層數(shù)之和最少单绑？
原始解法
初始數(shù)組設(shè)定每層樓的人數(shù)，遍歷所有樓層曹宴，統(tǒng)計(jì)最佳爬樓梯的層數(shù)最少,時(shí)間復(fù)雜度O(n2).
<pre><code>` func compute(person:[Int],maxFloor:Int) -> (Int,Int) {
var minFloor:Int = 0
var targetFloor:Int = 0
for i in 1...maxFloor { // 電梯停留在i層
var temp:Int = 0
for j in 1...maxFloor {
temp += person[j] * abs(i - j)
}
if i == 1 {
minFloor = temp
targetFloor = 1
} else {
if temp < minFloor {
minFloor = temp
targetFloor = i
}
}
}
return (minFloor,targetFloor)
}
`</code></pre>
最簡(jiǎn)單解法
假設(shè)N1為第i層以下的乘客數(shù)搂橙，N2為第i層的乘客數(shù)，N3為第i層以上的乘客數(shù)笛坦，已知乘客在第i層的nFloor值為count
如果電梯改停在i-1層時(shí)区转，那么此時(shí)nFloor值為count-N1+（N2+N3）
如果電梯改停在i+1層時(shí)苔巨，此時(shí)nFloor值為count+N1+N2-N3
由此可見N1+N2<N3時(shí)，停i+1層更好废离，這樣我們先計(jì)算第一層時(shí)的N1侄泽、N2、N3的值蜻韭，時(shí)間復(fù)雜度為O(n).
<pre><code>` func compute2(person:[Int],maxFloor:Int) -> (Int,Int) {
var n1:Int = 0 // 第i層以下的人數(shù)
var n2:Int = person[1] // 第i層的人數(shù)
var n3:Int = 0 // 第i層以上的人數(shù)
var countFloor:Int = 0 // 第i層的時(shí)候所走的樓層總數(shù)
var targetFloor:Int = 1
for i in 2...maxFloor {
countFloor += person[i] * (i - 1)
n3 += person[i]
}
// 如果樓層變?yōu)閕-1層 總層為 count + (n2 + n3 - n1)
// 如果樓層變?yōu)閕+1層 總層為 count + (n1 + n2 - n3)
for i in 2...maxFloor {
if n1+n2 < n3 {
targetFloor = i
countFloor += n1 + n2 - n3
n1 += n2 //n1 增加
n2 = person[i]
n3 -= person[i] // n3 減少
} else {
break
}
}
return (countFloor,targetFloor)
}`</code></pre>
測(cè)試代碼:
<pre><code>`var personFloor:[Int] = [0 ,2 , 3, 5, 10, 8, 6]
var elevator:Elevator = Elevator()
var result = elevator.compute(person: personFloor, maxFloor: 6)
print("FlyElephant-走的最小的路層--(result.0)--最佳樓層---(result.1)")
var result2 = elevator.compute2(person: personFloor, maxFloor: 6)
print("FlyElephant-走的最小的路層--(result2.0)--最佳樓層---(result2.1)")`</code></pre>
