# 0493. 翻转对
### 题目地址（493. 翻转对）
### 题目描述
```
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
示例 1:
输入: [1,3,2,3,1]
输出: 2
示例 2:
输入: [2,4,3,5,1]
输出: 3
注意:
给定数组的长度不会超过50000。
输入数组中的所有数字都在32位整数的表示范围内。
```
### 前置知识
* 归并排序
* 逆序数
* 分治
### 公司
* 阿里
* 百度
* 字节
### 暴力法
#### 思路
读完这道题你应该就能联想到逆序数才行。求解逆序数最简单的做法是使用双层循环暴力求解。我们仿照求解决逆序数的解法来解这道题（其实唯一的区别就是系数从 1 变成了 2）。
#### 代码
代码支持：Python3
Python3 Code:
```python
class Solution(object):
def reversePairs(self, nums):
n = len(nums)
cnt = 0
for i in range(n):
for j in range(i + 1, n):
if nums[i] > 2 * nums[j]:
cnt += 1
return cnt
```
### 分治法
#### 思路
如果你能够想到逆序数，那么你很可能直到使用类似归并排序的方法可以求解逆序数。实际上逆序数只是归并排序的副产物而已。
我们在正常的归并排序的代码中去计算逆序数即可。由于每次分治的过程，左右两段数组分别是有序的，因此我们可以减少一些运算。 从时间复杂度的角度上讲，我们从$O(N^2)$优化到了 $O(NlogN)$。
具体来说，对两段有序的数组，有序数组内部是不需要计算逆序数的。 我们计算逆序数的逻辑只是计算两个数组之间的逆序数，我们假设两个数组是 A 和 B，并且 A 数组最大的元素不大于 B 数组最小的元素。而要做到这样，我们只需要常规的归并排序即可。
接下来问题转化为求解两个有序数组之间的逆序数，并且两个有序数组之间满足关系`A数组最大的元素不大于B数组最小的元素`。
关于计算逆序数的核心代码(Python3):
```python
l = r = 0
while l < len(left) and r < len(right):
if left[l] <= 2 * right[r]:
l += 1
else:
self.cnt += len(left) - l
r += 1
```
#### 代码
代码支持：Python3
Python3 Code:
```python
class Solution(object):
def reversePairs(self, nums):
self.cnt = 0
def mergeSort(lst):
L = len(lst)
if L <= 1:
return lst
return mergeTwo(mergeSort(lst[:L//2]), mergeSort(lst[L//2:]))
def mergeTwo(left, right):
l = r = 0
while l < len(left) and r < len(right):
if left[l] <= 2 * right[r]:
l += 1
else:
self.cnt += len(left) - l
r += 1
return sorted(left+right)
mergeSort(nums)
return self.cnt
```
**复杂度分析**
* 时间复杂度：$O(NlogN)$
* 空间复杂度：$O(logN)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
对于具体的排序过程我们偷懒直接使用了语言内置的方法 sorted，这在很多时候是有用的，即使你是参加面试，这种方式通常也是允许的。省略非核心的考点，可以使得问题更加聚焦，这是一种解决问题的思路，在工作中也很有用。
### 关键点解析
* 归并排序
* 逆序数
* 分治
* 识别考点，其他非重点可以使用语言内置方法
### 扩展
这道题还有很多别的解法，感性的可以参考下这个题解 [General principles behind problems similar to "Reverse Pairs"](https://leetcode.com/problems/reverse-pairs/discuss/97268/General-principles-behind-problems-similar-to-%22Reverse-Pairs%22)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/493.reverse-pairs.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.