題目描述
學(xué)校在拍年度紀(jì)念照時(shí)，一般要求學(xué)生按照 非遞減 的高度順序排列。
請(qǐng)你返回至少有多少個(gè)學(xué)生沒有站在正確位置數(shù)量。該人數(shù)指的是：能讓所有學(xué)生以 非遞減 高度排列的必要移動(dòng)人數(shù)。
示例 1:
輸入：[1,1,4,2,1,3]
輸出：3
解釋：
高度為 4、3 和最后一個(gè) 1 的學(xué)生，沒有站在正確的位置。
提示：
- 1 <= heights.length <= 100
- 1 <= heights[i] <= 100
解法
由題可知，只需要獲得正確的非遞減序列，然后與當(dāng)前序列比較即可獲得需要移動(dòng)的個(gè)數(shù)。
sort排序比較
對(duì)序列進(jìn)行排序，獲得非遞減序列，逐個(gè)元素比較。
class Solution:
def heightChecker(self, heights: List[int]) -> int:
arr=sorted(heights)
ret=0
for i in range(len(heights)):
if heights[i]!=arr[i]:
ret+=1
return ret
計(jì)數(shù)排序比較
根據(jù)提示可知元素值范圍不大，不妨申請(qǐng)一定值域范圍的序列 arr，存儲(chǔ)對(duì)應(yīng)元素值出現(xiàn)的個(gè)數(shù)，此時(shí)遍歷 arr 即可獲得非遞減序列，仍然與原序列進(jìn)行逐個(gè)元素對(duì)比，獲取移動(dòng)個(gè)數(shù)。
此處元素值范圍不大，可以每個(gè)桶只存儲(chǔ)一個(gè)元素值對(duì)應(yīng)的內(nèi)容，當(dāng)值空間較大時(shí)，可以針對(duì)每個(gè)桶映射一定元素值范圍的內(nèi)容，在桶內(nèi)可以自由搭配其他的排序算法。
class Solution:
def heightChecker(self, heights: List[int]) -> int:
arr=[0]*101
for e in heights:
arr[e]+=1
index,ret=0,0
for i in range(1,101):
while arr[i]>0:
if i!=heights[index]:
ret+=1
arr[i]-=1
index+=1
return ret
