上一篇:?算法隨筆_11: 字符串的排列-CSDN博客

題目描述如下:

給你一個(gè)整數(shù)數(shù)組 nums ，你需要找出一個(gè) 連續(xù)子數(shù)組 ，如果對(duì)這個(gè)子數(shù)組進(jìn)行升序排序，那么整個(gè)數(shù)組都會(huì)變?yōu)樯蚺判颉Ｕ?qǐng)你找出符合題意的最短子數(shù)組，并輸出它的長(zhǎng)度。

示例 1：

輸入：nums = [2,6,4,8,10,9,15]

輸出：5

解釋：你只需要對(duì) [6, 4, 8, 10, 9] 進(jìn)行升序排序，那么整個(gè)表都會(huì)變?yōu)樯蚺判颉?/p>

===================

我們一起來(lái)分析一下這道題。

需要找出的這個(gè)子數(shù)組可以是任意的位置。不失一般性的，我們可以假設(shè)這個(gè)子數(shù)組的起始點(diǎn)在原來(lái)數(shù)組的中間某處。我們假設(shè)這個(gè)子數(shù)組為nums_mid，那么此時(shí)它分割出來(lái)左右兩個(gè)子數(shù)組分別為nums_left，nums_right。按照題意，如果對(duì)子數(shù)組nums_mid進(jìn)行升序排序，整個(gè)數(shù)組都會(huì)變?yōu)樯蚺判?#xff0c;那么原數(shù)組應(yīng)該有以下的特征:

僅對(duì)子數(shù)組nums_mid進(jìn)行升序排序，就相當(dāng)于對(duì)全數(shù)組進(jìn)行了排序。反過(guò)來(lái)說(shuō)，對(duì)全數(shù)組進(jìn)行排序，其實(shí)只是把nums_mid進(jìn)行了排序。在排序的前后，nums_left，nums_right兩個(gè)子數(shù)組的序列是不變的。

基于此特征，我們可以寫(xiě)出如下算法:

我們對(duì)原數(shù)組進(jìn)行升序排序。排序之后，我們把排序之后的數(shù)組與原數(shù)組從左到右逐個(gè)字符的進(jìn)行比較。當(dāng)發(fā)現(xiàn)第一個(gè)出現(xiàn)不同的字符時(shí)，我們就找到了nums_left。同理，從右至左逐個(gè)字符的進(jìn)行比較，我們就找到nums_right。那么，中間的這一塊兒就是nums_mid。其長(zhǎng)度即可算出。

此算法的時(shí)間復(fù)雜度為O(nlogn) 。

==================

讓我們?cè)倏紤]一下有沒(méi)有更優(yōu)的算法？

讓我們重新審視一下原題的描述。nums_mid不論是否排序，它里面的任何一個(gè)元素都比nums_left中的任何一個(gè)元素大。nums_right在排序前后本身就不改變序列，因此，它的任何一個(gè)元素也比nums_left的任何一個(gè)元素大。因此，nums_left有如下特征:

1.?它是一個(gè)升序排列。

2. 它的最大值一定比后面所有數(shù)的最小值還要小。

基于此特征，我們可以給出如下的算法:

1. 我們?cè)O(shè)置兩個(gè)變量，nums_left_max(表示nums_left的最大值的下標(biāo))，和left_min(表示nums_left后面所有數(shù)的最小值)。

2. 我們從右向左遍歷原數(shù)組，記錄當(dāng)前已經(jīng)遍歷過(guò)的元素的最小值left_min。并且每個(gè)當(dāng)前訪問(wèn)的元素e和left_min比較，會(huì)有下面兩種情況:

? ?a. 如果e小于left_min，并且nums_left_max為-1，我們記錄當(dāng)前下標(biāo)為nums_left_max。

? ?b. 如果e大于left_min，那么nums_left_max肯定不為當(dāng)前的下標(biāo)。我們把nums_left_max重置為1。

遍歷完成后我們就找到了nums_left_max。

同理，我們可以求出nums_right_min(表示nums_right的最小值的下標(biāo))。

最終兩數(shù)相減即為題目答案。由于此算法只執(zhí)行了一次遍歷，因此時(shí)間復(fù)雜度為O(N) 。

算法具體實(shí)現(xiàn)時(shí)注意一下邊界條件。實(shí)際代碼如下:

class Solution(object):def findUnsortedSubarray(self, nums):n=len(nums)nums_left_max=-1nums_right_min=nleft_min=float('inf')right_max=float('-inf')for i in range(n):if right_max<=nums[i]:right_max=nums[i]if nums_right_min==n:nums_right_min=ielse:nums_right_min=nif left_min>=nums[n-i-1]:left_min=nums[n-i-1]if nums_left_max==-1:nums_left_max=n-i-1else:nums_left_max=-1ret=nums_right_min-nums_left_max-1ret=0 if ret<0 else retreturn ret