剣指offerシリーズ-面接問題51.配列内の逆シーケンスペア(python)

文書ディレクトリ

1. タイトル

2. 解題構想

2.1暴力法

2.3動的計画

2.3分治思想(集計並べ替え統計逆序数による)

3. コード実装

3.1暴力法

3.2動的計画

3.3分治思想(集計並べ替え統計逆序数による)

4. まとめ

5. 参考文献

1.テーマ
配列内の2つの数値で、前の1つの数値が後の数値より大きい場合、この2つの数値は逆シーケンスペアを構成します.配列を入力して、この配列の中の逆順序の対の総数を求めます
2.問題の解き方
詳細は暴力解法、分治思想、樹状配列を参照
2.1暴力法
これは何も言うことはない.
2.3動的計画
f(n)=f(n−1)+mであり、前の配列における現在の要素より大きい要素の個数.
2.3分治思想(集計ソートによる統計逆序数)
説明:このアルゴリズムを理解するには、「集計ソート」に詳しい必要があります.再帰関数を記述すると、毎回2つの分割配列のサブ区間に分割され、メソッドスタックがポップアップされると、2つの秩序配列が1つずつ結合され、最後にソート作業が完了することを把握します.
3.コード実装
3.1暴力法
O(n 2),空間複雑度S(n),タイムアウト.

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        size = len(nums)
        if size < 2:
            return 0
        res = 0
        for i in range(0, size - 1):
            for j in range(i + 1, size):
                if nums[i] > nums[j]:
                    res += 1
        return res

3.2動的計画
O(n 2),空間複雑度S(n),タイムアウト.

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        """
        1.     
                   ：
                f(i) = f(i-1) + m；m         nums[i]       
        """
        def count_large_number(arr, elem):
            count = 0
            for val in arr:
            	if val > elem:
            		count += 1
            return count
        
        if not nums: return 0
        dp, i = [0 for i in nums], 1

        while i < len(nums):
            m = count_large_number(nums, nums[i])
            dp[i] = dp[i-1] + m
            i += 1

        return dp[-1]

3.3分治思想(集計並べ替えによる統計逆序数)

class Solution:

    def reversePairs(self, nums: List[int]) -> int:
        size = len(nums)
        if size < 2:
            return 0

        #          
        temp = [0 for _ in range(size)]
        return self.count_reverse_pairs(nums, 0, size - 1, temp)

    def count_reverse_pairs(self, nums, left, right, temp):
        #     nums     [left, right]      
        if left == right:
            return 0
        mid = (left + right) >> 1
        left_pairs = self.count_reverse_pairs(nums, left, mid, temp)
        right_pairs = self.count_reverse_pairs(nums, mid + 1, right, temp)

        reverse_pairs = left_pairs + right_pairs
        #          ，[left, mid]   [mid + 1, right]                

        if nums[mid] <= nums[mid + 1]:
            #                 ，     reverse_pairs
            return reverse_pairs

        reverse_cross_pairs = self.merge_and_count(nums, left, mid, right, temp)
        return reverse_pairs + reverse_cross_pairs

    def merge_and_count(self, nums, left, mid, right, temp):
        """
        [left, mid]   ，[mid + 1, right]   

         ：[2, 3, 5, 8]， ：[4, 6, 7, 12]
                     ，                 ，
          " "   " "     ，
          " "          mid - i + 1    " "                   

        """
        for i in range(left, right + 1):
            temp[i] = nums[i]

        i = left
        j = mid + 1
        res = 0
        for k in range(left, right + 1):
            if i > mid:
                nums[k] = temp[j]
                j += 1
            elif j > right:
                nums[k] = temp[i]
                i += 1
            elif temp[i] <= temp[j]:
                #          ，      
                nums[k] = temp[i]
                i += 1
            else:
                # assert temp[i] > temp[j]
                #          ，     ，      ，                  
                nums[k] = temp[j]
                j += 1
                #  ：[7, 8, 9][4, 6, 9]，4   7    7             
                res += (mid - i + 1)
        return res

  ：liweiwei1419
  ：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/bao-li-jie-fa-fen-zhi-si-xiang-shu-zhuang-shu-zu-b/
  ：  （LeetCode）
        。             ，          。

4.まとめ
この問題は私にはできません.
5.参考文献
[1]剣指offer叢書[2]剣指Offer-名企業面接官精講典型プログラミング問題[3]暴力解法、分治思想、樹状配列