LeetCode 翻转对题解

LeetCode 翻转对题解题目描述给定一个数组 nums如果 i j 且 nums[i] 2*nums[j]则 (i, j) 称为一个翻转对。返回翻转对的数量。示例输入nums [1,3,2,3,1]输出2解题思路方法分治思路使用归并排序的思想计算翻转对。在归并排序的合并阶段计算翻转对的数量。由于左右两部分已经排序所以可以高效计算。复杂度分析时间复杂度O(n log n)。空间复杂度O(n)。代码实现def reverse_pairs(nums): def helper(left, right): if left right: return 0 mid (left right) // 2 count helper(left, mid) helper(mid 1, right) j mid 1 for i in range(left, mid 1): while j right and nums[i] 2 * nums[j]: j 1 count j - (mid 1) nums[left:right1] sorted(nums[left:right1]) return count return helper(0, len(nums) - 1) # 测试 def test_reverse_pairs(): nums [1, 3, 2, 3, 1] print(reverse_pairs(nums)) # 输出2 if __name__ __main__: test_reverse_pairs()总结翻转对是分治思想的典型应用在归并排序过程中计算翻转对的数量。