91超碰碰碰碰久久久久久综合_超碰av人澡人澡人澡人澡人掠_国产黄大片在线观看画质优化_txt小说免费全本

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

劍指offer:數組中的逆序對

發布時間:2020-08-03 12:15:42 來源:網絡 閱讀:620 作者:Jayce_SYSU 欄目:編程語言

題目描述
在數組中的兩個數字,如果前面一個數字大于后面的數字,則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。并將P對1000000007取模的結果輸出。 即輸出P%1000000007
輸入描述:
題目保證輸入的數組中沒有的相同的數字

數據范圍:

    對于%50的數據,size<=10^4

    對于%75的數據,size<=10^5

    對于%100的數據,size<=2*10^5

示例1
輸入 1,2,3,4,5,6,7,0
輸出 7

# -*- coding: utf-8 -*-
# @Time         : 2019-07-12 11:39
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : inversePairs.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class Solution:
    """
    要計算數組中的逆序對的對數,那么最直觀的做法就是遍歷整個數組,將當前元素和后續的所有元素進行
    比較,然后累計有多少逆序對。

    另一種解法就是基于歸并排序的解法。
    上述的解法的最大缺陷在于每個數字都要跟后續的所有數字進行比較,導致時間復雜度為O(n^2)。
    如果可以避免這么多次比較,就可以提高效率。
    效仿歸并排序,我們先將一個數組不斷對半分裂,先得到多個長度為1的數組,然后每兩個相鄰數組進行比較
    然后歸并。
    **之所以要進行歸并(將這兩個相鄰數組合并后排序)是因為如果不排序的話,在下一輪的比較的時候會出現
    重復計數的情況**
    由于進行了排序,在下一輪歸并的時候只需要將兩個數組的最大值進行比較,如果左邊的數組的最大值大于
    右邊數組的最大值,那么說明右邊整個數組都可以跟左邊數組的最大值組成逆序對,因此跳過左邊數組最大
    值和右邊剩余元素的比較。
    這種解法其實就是**降序的歸并排序**。
    """

    def InversePairs(self, data):
        def split(start, end):
            # 先將整個數組對半分裂成若干個長度為1的數組
            if start < end:  # start < end,說明長度大于1,繼續分裂
                mid = (start + end) >> 1
                split(start, mid)
                split(mid + 1, end)
                # 分裂完成后,對兩個相鄰數組進行歸并
                # 兩個數組的下標分別為[start, mid], [mid + 1, end]
                merge(start, mid, end)

        def merge(start, mid, end):
            # 由于我們這里的count是InversePairs()里的局部變量,
            # 所以用nonlocal關鍵字而非global
            nonlocal count
            # 由于是進行降序歸并,因此從兩個數組的末尾開始歸并
            p1 = mid
            p2 = end
            while p1 >= start and p2 > mid:
                # 如果左邊大于右邊,說明組成了一個逆序對,
                # 計數器count增加數值為右邊數組的剩余元素個數
                if data[p1] > data[p2]:
                    # count += end - p2 + 1
                    count += p2 - mid
                    # data_copy用于存儲歸并后的結果
                    data_copy.append(data[p1])
                    p1 -= 1
                else:
                    data_copy.append(data[p2])
                    p2 -= 1
            # 將左右數組剩余的元素加入data_copy中,由于是有其中一個數組完全為空了,所以事實上
            # 只將其中一個數組的元素加入data_copy中,而由于我們是利用遞歸實現的,這個數組也早
            # 已有序,因此歸并后的結果data_copy是有序的
            for p in range(p1, start - 1, -1):
                data_copy.append(data[p])
            for p in range(p2, mid, -1):
                data_copy.append(data[p])
            # 將歸并結果賦值到原數組中,注意這里賦值的順序,我們要保證從小到大。
            while data_copy:
                data[start] = data_copy.pop(-1)
                start += 1

        if not data:
            return 0

        count = 0  # 用于統計逆序對的對數
        data_copy = []  # 輔助數組,用于存儲兩個相鄰數組歸并的臨時結果
        split(0, len(data) - 1)
        return count % 1000000007

def main():
    solution = Solution()
    data = [364, 637, 341, 406, 747, 995, 234, 971, 571, 219, 993, 407, 416,
            366, 315, 301, 601, 650, 418, 355, 460, 505, 360, 965, 516, 648,
            727, 667, 465, 849, 455, 181, 486, 149, 588, 233, 144, 174, 557, 67,
            746, 550, 474, 162, 268, 142, 463, 221, 882, 576, 604, 739, 288,
            569, 256, 936, 275, 401, 497, 82, 935, 983, 583, 523, 697, 478, 147,
            795, 380, 973, 958, 115, 773, 870, 259, 655, 446, 863, 735, 784, 3,
            671, 433, 630, 425, 930, 64, 266, 235, 187, 284, 665, 874, 80, 45,
            848, 38, 811, 267, 575]
    # data = [1,2,3,4,5,6,7,0]
    print(solution.InversePairs(data))

if __name__ == '__main__':
    main()
向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

财经| 吉水县| 台北市| 平潭县| 大竹县| 讷河市| 象山县| 丰镇市| 藁城市| 沂南县| 黄浦区| 眉山市| 资讯| 武穴市| 乌恰县| 阳江市| 灵石县| 海原县| 辽中县| 沈丘县| 扶绥县| 岑溪市| 府谷县| 五峰| 成安县| 伊川县| 宜城市| 恩施市| 普陀区| 迭部县| 苗栗市| 永靖县| 郧西县| 桦南县| 五原县| 长宁县| 曲阜市| 如皋市| 宁陕县| 巴彦县| 浦县|