581.最短無秩序連続サブ配列(Python)

タイトル
難易度:★☆☆☆タイプ:配列
整数配列を指定するには、連続したサブ配列を探す必要があります.このサブ配列を昇順ソートすると、配列全体が昇順ソートになります.
見つけたサブ配列は最も短いはずです.その長さを出力してください.
入力された配列の長さ範囲は[1,10000]であることを示します.入力された配列には重複要素が含まれる可能性があるので、昇順は<=を意味します.
例
例1:入力:[2,6,4,8,10,9,15]出力:5解釈:[6,4,8,10,9]を昇順ソートするだけで、テーブル全体が昇順ソートになります.
に答える
並べ替えが必要なサブストリングの最小長を探すために、配列を並べ替えてから、両端から中間に比較して、どの位置から異なるかを見ることができます.

入力配列を先にソートするには、ソート後の配列が元の配列と同じかどうかを判断する必要があります.同じ説明でサブ配列をソートする必要がなければ、直接ゼロに戻ればいいです.

左ポインタを定義し、ゼロから右にスライドし、元の配列とソート後の配列のポインタでの値を逐一比較し、異なる値に遭遇した場合、ソートが必要なサブ配列の最左端に相当し、その位置を記録し、スライドを停止する.同様に、右から左にスライドする右ポインタを定義し、初めて異なる位置が現れたことを記録する.

は,左右のポインタの位置から並べ替えが必要な最短の無秩序サブ配列の長さを算出することができ,ここでは結果を+1すればよいことに注意する.

class Solution:
    def findUnsortedSubarray(self, nums):
        sorted_nums = sorted(nums)                  #       

        if sorted_nums == nums:                     #          
            return 0                                #          

        left = 0                                    #       
        while True:
            if nums[left] != sorted_nums[left]:     #           
                break                               #     
            left += 1                               #      

        right = len(nums) - 1                       #       
        while True:
            if nums[right] != sorted_nums[right]:   #           
                break                               #     
            right -= 1                              #      

        return right - left + 1                     #            

以下は、上記の方法のコンパクトな書き方です.

class Solution:
    def findUnsortedSubarray(self, nums):
        #                        ，     
        diff = [i for i, (a, b) in enumerate(zip(nums, sorted(nums))) if a != b]
        #        ，                    ，     
        return len(diff) and max(diff) - min(diff) + 1

質問やアドバイスがあれば、コメントエリアへようこそ~