LeetCode如何找出數(shù)組中的逆序?qū)?/h1>

發(fā)布時間：2021-12-15 13:58:25 來源：億速云 閱讀：143 作者：小新 欄目：大數(shù)據(jù)

這篇文章主要介紹LeetCode如何找出數(shù)組中的逆序?qū)?，文中介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們一定要看完！

題目描述

在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)?。輸入一個數(shù)組，求出這個數(shù)組中的逆序?qū)Φ目倲?shù)。

0 <= 數(shù)組長度 <= 50000

           

題目樣例

           

示例

• 輸入: [7,5,6,4]
• 輸出: 5

           

題目思考

1. 如何批量得到逆序?qū)?

           

解決方案

           

思路

• 一個比較容易想到的思路是雙重循環(huán), 暴力求逆序?qū)? 但這樣時間復(fù)雜度是 O(N^2), 根據(jù)數(shù)據(jù)規(guī)?？隙ǔ瑫r, 如何進(jìn)行優(yōu)化呢?
• 如果我們能將問題進(jìn)行分解, 先求出數(shù)組左右兩部分的逆序?qū)?shù)目, 最后再一次遍歷將分屬兩部分的逆序?qū)?也即第一個數(shù)在左半部分, 第二個數(shù)在右半部分)也求出來并累加在一起, 這樣就能優(yōu)化時間復(fù)雜度到 O(NlogN), 這就是分治法的思想
• 此時關(guān)鍵在于如何一次遍歷就求得分屬兩部分的逆序?qū)δ? 如果左右兩部分是有序的就很好辦了, 可以利用歸并排序的思路, 雙指針遍歷, 哪邊小就把哪邊加入結(jié)果數(shù)組中. 如果是右側(cè)小的話就意味著左側(cè)剩余的數(shù)字都和當(dāng)前右側(cè)數(shù)字構(gòu)成逆序?qū)? 將對應(yīng)的數(shù)目加入結(jié)果中即可.
• 而左右部分有序正好也是歸并排序的結(jié)果, 所以整個思路就是在歸并排序的基礎(chǔ)上加上逆序?qū)Φ慕y(tǒng)計
• 下面代碼對必要的步驟有詳細(xì)的解釋, 方便大家理解

           

復(fù)雜度

• 時間復(fù)雜度 O(NlogN): 使用了歸并排序, 時間復(fù)雜度是( N+(N/2)*2+(N/4)*4+...+1*N = NlogN, 因為一共 logN 個乘積)
• 空間復(fù)雜度 O(N): 歸并排序需要用到臨時數(shù)組, 長度為 N

           

代碼

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.res = 0

        def mergesort(s, e):
            if s >= e:
                return
            m = (s + e) >> 1
            # 先排序并統(tǒng)計左右部分
            mergesort(s, m)
            mergesort(m + 1, e)
            # 使用臨時數(shù)組存儲排序好的左右部分
            # 注意這里選擇逆序存儲, 是因為可以利用O(1)的pop操作得到最小的元素
            # 當(dāng)然這里也可以使用雙端隊列, 這樣就無需逆序了
            left = nums[s:m + 1][::-1]
            right = nums[m + 1:e + 1][::-1]
            for i in range(s, e + 1):
                if not right or left and left[-1] <= right[-1]:
                    # 當(dāng)前左側(cè)數(shù)字更小或者右側(cè)數(shù)字已經(jīng)用完, 此時不構(gòu)成逆序?qū)?br/>                    nums[i] = left.pop()
                else:
                    # 當(dāng)前右側(cè)數(shù)字更小, 和剩余的左側(cè)部分都構(gòu)成逆序?qū)?br/>                    self.res += len(left)
                    nums[i] = right.pop()

        mergesort(0, len(nums) - 1)
        return self.res

以上是“LeetCode如何找出數(shù)組中的逆序?qū)Α边@篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道！