493.md

493 Reverse Pairs

Description

link

---

Solution

• 为什么使用Merge sort来做
  • merge sort可以在保证index顺序不变的情况下，让所有的元素进行交互
• 为什么可以work
  • 在手动merge的过程中，因为左边和右边部分都已经排序好，所以只需要从两边的一开始分别从前往后遍历，当左边不满足pair条件的时候左边前进，否则右边前进
• 为什么不会有重复
  • 因为当sort进入到上一层的时候，上一层的交互对象已经变化了，当前已经排序好的内容不会再进行比较，所以不会有重复出现

---

Code

O(nlog(n))

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.cnt = 0
        
        def msort(lst):
            # merge sort body
            L = len(lst)
            if L <= 1:                          # base case
                return lst
            else:                               # recursive case
                return merger(msort(lst[:int(L/2)]), msort(lst[int(L/2):]))
        def merger(left, right):
            # merger
            l, r = 0, 0                         # increase l and r iteratively
            while l < len(left) and r < len(right):
                if left[l] <= 2*right[r]:
                    l += 1
                else:
                    self.cnt += len(left)-l     # add here
                    r += 1
            return sorted(left+right)           # I can't avoid TLE without timsort...

        msort(nums)
        return self.cnt