交易逆序对的总数-LeetCode

交易逆序对的总数

🎯 问题描述（来源于LeetCode）

描述：
在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
说明：

• 0 <= record.length <= 50000

示例：

• 示例 1：

输入：record = [9, 7, 5, 4, 6]
输出：8
解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

💻 解题思路

思路1：暴力破解

思路1：代码实现

class Solution:
    def reversePairs(self, record: List[int]) -> int:
        i=count=0
        while i<len(record):
            for d in range(i,len(record)):
                if record[i]>record[d]:
                    count+=1
            i+=1
        return count

思路1：📊 性能分析

提交结果

• 运行时间：超时
• 内存消耗：

复杂度验证

• 时间复杂度：$O(N^2))$
• 空间复杂度：$O(1)$

思路2：归并

思路2：代码实现

class Solution:
    def reversePairs(self, record: List[int]) -> int:
        return self.merge_sort(record)[1]
    def merge_sort(self, nums):
        if len(nums) <= 1:
            return nums, 0
        mid = len(nums) // 2
        left, left_count = self.merge_sort(nums[:mid])
        right, right_count = self.merge_sort(nums[mid:])
        
        merged, merge_count = self.merge(left, right)
        return merged, left_count + right_count + merge_count
    
    def merge(self, left, right):
        result = []
        i = j = 0
        count = 0
        
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                # 计算逆序对
                count += len(left) - i
                j += 1
        
        result.extend(left[i:])
        result.extend(right[j:])
        
        return result, count

思路2：📊 性能分析

提交结果

• 运行时间：663ms击败57.22%
• 内存消耗：23.94MB击败65.88%

复杂度验证

• 时间复杂度：$O(Nlogn)$
• 空间复杂度：$O(N)$

思考