題目：給定一個(gè)無序數(shù)組，求出需要排序的最短子數(shù)組長度

例如：arr = [1,5,3,4,2,6,7] 返回4，因?yàn)橹挥衃5,3,4,2]需要排序

解決這個(gè)問題可以做到時(shí)間復(fù)雜度為O(N)，額外空間復(fù)雜度為O(1)

初始化變量noMinIndex = -1,從右向左遍歷，遍歷的過程中記錄右側(cè)出現(xiàn)過的數(shù)的最小值，標(biāo)記為min_。假設(shè)當(dāng)前數(shù)為arr[i],如果arr[i] > min，說明如果要整體有序，min_值必須會(huì)移動(dòng)到arr[i]的左邊。用noMinIndex記錄最左邊出現(xiàn)這種情況的位置。如果遍歷完成后，noMinIndex依然等于－1，說明從右到左始終不升序，原數(shù)組本來就有序，直接返回0，即完全不需要排序。

接下來從左向右遍歷，遍歷的過程中記錄左側(cè)出現(xiàn)過的數(shù)的最大值，標(biāo)記為max_。假設(shè)當(dāng)前數(shù)為arr[i]，如果arr[i] < max, 說明如果排序，max值必然會(huì)移動(dòng)到arr[i]的右邊。用變量noMaxIndex 記錄最右邊出現(xiàn)這種情況的位置

遍歷完成后，arr[noMinIndex,noMaxindex]是真正需要排序的部分，返回長度即可

def getMinLength(L):if L == None or len(L) <2:returnmin_ = L[len(L)-1]noMinIndex = -1for i in range(len(L)-2,0,-1):if L[i] > min_:noMinIndex = ielse:min_ = min(L[i],min_)if noMinIndex == -1:return 0max_ = L[0]noMaxIndex = -1for i in range(1,len(L)):if L[i] > max_:max_ = max(L[i],max_)else:noMaxIndex = ireturn noMaxIndex - noMinIndex + 1

?

總結(jié)

以上是生活随笔為你收集整理的需要排序的最短子数组长度的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。