https://leetcode.com/problems/reverse-pairs/
很经典的题目。
当然这道题还可以用线段树或者BIT做，不过归并排序在这道题里很经典了。

个人解答

  1. class Solution:
  2.     def reversePairs(self, nums: List[int]) -> int:
  3.         self.tmp = [0] * len(nums)
  5.         def mergeSortAndCount(arr, l, r):
  6.             if l >= r:
  7.                 return 0
  8.             mid = (l + r) // 2
  9.             res = 0
  10.             res += mergeSortAndCount(arr, l, mid) + mergeSortAndCount(arr, mid + 1, r)
  12.             j = mid + 1
  13.             for i in range(l, mid + 1):
  14.                 while j <= r and nums[j] * 2 < nums[i]:
  15.                     j += 1
  16.                 res += j - (mid + 1)
  18.             # merge
  19.             # i, j = l, mid + 1
  20.             # ti = l
  21.             # while ti <= r:
  22.             #     if j > r or (i <= mid and nums[i] <= nums[j]):
  23.             #         self.tmp[ti] = nums[i]
  24.             #         i += 1
  25.             #     else:
  26.             #         self.tmp[ti] = nums[j]
  27.             #         j += 1
  28.             #     ti += 1
  29.             # for i in range(l, r + 1):
  30.             #     arr[i] = self.tmp[i]
  32.             # direct sort, faster than merge???
  33.             arr[l:r + 1] = sorted(arr[l:r + 1])
  35.             return res
  37.         return mergeSortAndCount(nums, 0, len(nums) - 1)

题目分析

分治的思想，一旦想到，应该就比较清晰了。左右sort好之后，只要左右各遍历一遍，就能够得出想要的结果。

一个有趣的地方在于，手写的merge，竟然比直接sort要慢很多，这就很尴尬了。
不过还是有必要记录下来归并的模板，快速写出来，注意题目中条件的判断：

  1. if j > r or (i <= mid and nums[i] <= nums[j])

如果只想写一个ifelse，那么这个条件，i和j的范围都要写好。
另外，提前开一个等大的临时数组存放临时结果，不要递归的时候创建，这样反复创建释放比较费时间。