题目大意：
给定一个数组 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位整数的表示范围内。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=493
解题思路：
这道题使用全体遍历循环的暴力算法肯定超时，所以考虑再三还是采用归并排序算法比较靠谱，归并排序英文叫做merge sort，顾名思义，边递归边排序。这里先要啰嗦几句归并排序的算法，因为这是本题的核心部分，当然老司机可以跳过。
归并排序的核心首先在于拆分数组，通常情况下会将数组从中间一分为二，如果数组的元素数为偶数，那么，拆分后的两个数组个数相同，如果是奇数，那么其中一个子数组的元素数会比另一个大1。
其次，要考虑到递归，因为数组只拆分一次不足以将整个数组排序，要把复杂问题简单化就要将数组拆分到极致。什么是极致，很简单，如果拆分后的两个数组分别只有一个元素，或是其中一个子数组有1个元素，另一个子数组为空，这时做排序比较就很简单了。比如：leftArray = {5}, rightArray={3}，或者：leftArray = {5}, rightArray={}
假定我们需要将数组按照从小到大的正序排列，那么，我们可以新建一个数组int[] tempNums，作为排序后的新数组。这时只要比较两边的数字，先将小的一个放入新数组，再将大的放入数组tempNums，这样就完成了排序工作。当然，如果其中一个子数组为空，那么只要将存在元素的那个数组存入新数组就可以了。
因为使用了递归拆分数组并进行排序，所以数组会从最小的单元逐级向上进行排序，直到整个数组排序完成。大体的实现顺序如下所示
int num[] = {4,6,3,2,7,9,5,1};
// 递归拆分
{4,6,3,2} {7,9,5,1}
{4,6} {3,2} {7,9} {5,1}
{4} {6} {3} {2} {7} {9} {5} {1}
// 递归排序
{4}{6} {3}{2} {7}{9} {5}{1} ⇒ {4，6} {2，3} {7，9} {1，5}
{4，6} {2，3} {7，9} {1，5} ⇒ {2，3，4，6} {1，5，7，9}
{2，3，4，6} {1，5，7，9} ⇒ {1，2，3，4，5，6，7，9}归并排序的实现代码：
// 起始start为0，end为数组长度-1
public void find(int[] nums, int start, int end) {
if (start >= end) {
return;
}
// 数组中间index
int middle = (end + start) / 2;
int leftArrayStart = start; // 拆分后左边子数组起始点
int leftArrayEnd = middle; // 拆分后左边子数组终点
int rightArrayStart = middle + 1; // 拆分后右边子数组起始点
int rightArrayEnd = end; // 拆分后右边子数组终点
// 继续递归拆分左边子数组
find(nums, leftArrayStart, leftArrayEnd);
// 继续递归拆分右边子数组
find(nums, rightArrayStart, rightArrayEnd);
// 定义一个临时数组用于存放两个子数组合并排序后的数组
int[] tempNums = new int[end - start + 1];
int i = 0;
// 因为两边数组都是分别排序好的，所以合并排序比较简单
while (leftArrayStart <= leftArrayEnd && rightArrayStart <= rightArrayEnd) {
// 如果左边的数小于右边的，那么将左边的数放入临时数组中。
// 同时左边起始index加一
// 反之则将右边数字放入临时数组，同时右边起始index加一
// 直到一边数组全部放入临时数组中为止
if (nums[leftArrayStart] < nums[rightArrayStart]) {
tempNums[i] = nums[leftArrayStart];
leftArrayStart++;
} else {
tempNums[i] = nums[rightArrayStart];
rightArrayStart++;
}
i++;
}
// 如果左边数组有剩余，则将左边数组剩余的元素全部放入临时数组
while (leftArrayStart <= leftArrayEnd) {
tempNums[i] = nums[leftArrayStart];
leftArrayStart++;
i++;
}
// 如果右边数组有剩余，则将右边数组剩余的元素全部放入临时数组
while (rightArrayStart <= rightArrayEnd) {
tempNums[i] = nums[rightArrayStart];
rightArrayStart++;
i++;
}
// 将排序好的临时数组更新到原数组中
for (int j = 0; j < tempNums.length; j++) {
nums[start + j] = tempNums[j];
}
}到此为止，归并排序算法的思路就非常清晰了。那么回到本题，如何利用该算法找到所有的翻转对呢？其实通过上面的find()函数的代码，我们可以得到几个比较有用的信息：
第一，递归排序的执行循序是，先将大数组一步一步的拆分成最小数组，然后再一步一步的将小数组合并排序成大数组的一个过程。因此，拆分后的两个数组分别是有序排列的（从小到大）。
第二，根据第一点，我们可以想到，问题其实变得简单了，我们循环左边子数组的元素，如果该元素比右边子数组的某个元素大两倍以上的话，那么我们就找到了一个翻转对，同时将右边的数组index加一继续向后寻找，直到没有翻转对出现时，左边数组index加一，继续执行同样的比较，直到循环结束为止，这样，所有翻转对就都可以被找到。不过，有人会问，为什么左边子数组中的元素不需要在左边的子数组中找翻转对呢？因为我们采用的递归算法，不论左边还是右边的子数组都会再次被拆分执行同样的逻辑，因此不需要在同数组中寻找答案。
第三，算法可以稍微进行优化，因为左右两边的子数组都是进行过排序的，所以，当Left[i] * 2 > Right[j]时，那么 Left[i + 1] * 2也一定大于 Right[j]。这样在进行循环时，每当右边的数组index加一后，右边数组的index是不需要重置的。
第四，最后有个小细节需要注意一下，因为用到了乘法 (*2)操作，所以应考虑到int类型乘以2会超过int最大值，所以结果应转为long型比较。
思路讲完了，最后还是看看完整的代码吧：
public int reversePairs(int[] nums) {
// 返回结果，翻转对总个数
int res = 0;
// 数组的长度
int length = nums.length;
// 数组为空还找个毛线
if (length <= 1) {
return res;
}
// 利用归并排序算法查找所有翻转对
return find(nums, 0, nums.length - 1);
}
public int find(int[] nums, int start, int end) {
// 找到的翻转对个数
int result = 0;
// 当起始位和结束位相同时，说明已将数组拆分至极致，结束递归
if (start >= end) {
return 0;
}
// 找到数组的中间位
int middle = (end + start) / 2;
// 分别递归寻找左右两个数组中存在的翻转对个数
result = find(nums, start, middle) + find(nums, middle + 1, end);
// 以下代码为寻找左右两个数组之间存在的翻转对个数
int leftArrayStart = start; // 拆分后左边子数组起始点
int leftArrayEnd = middle; // 拆分后左边子数组终点
int rightArrayStart = middle + 1; // 拆分后右边子数组起始点
int rightArrayEnd = end; // 拆分后右边子数组终点
// 循环左边数组，直到起始点等于终点为止
while (leftArrayStart <= leftArrayEnd) {
// 如果左边数组当前元素是右边数组当前元素的2倍以上
if ((long) nums[leftArrayStart] > (long) nums[rightArrayStart] * 2) {
// 右边数组起始位加一继续向后寻找
rightArrayStart++;
// 如果加一后右边数组越界，则取消加一操作
// 将右边数组起始inex设为结束index即可
if (rightArrayStart > rightArrayEnd) {
rightArrayStart = rightArrayEnd;
// 因为数组是从小到大排序的，
// 所以右数组当前数之前的数字均小于当前数字，
// 所以之前的所有数字均为左数组当前数字的翻转对
// 当前左边数组元素找到的翻转对个数应该为：
// 右边数组的起始index数。
result += (rightArrayStart - middle);
// 因为有数组已经到头，所以左数组加一继续循环
leftArrayStart++;
}
} else {
// 如果做数组当前数不是有数组当前数的两倍以上
// 那么有数组当前index之前的数都是左数组当前数的翻转对
result += (rightArrayStart - middle - 1);
//左数组加一继续循环
leftArrayStart++;
}
}
// 到此为止，翻转对查找工作已经完成，接下来是归并排序逻辑，为了之后的递归处理做准备。
leftArrayStart = start;
rightArrayStart = middle + 1;
int[] tempNums = new int[end - start + 1];
int i = 0;
while (leftArrayStart <= leftArrayEnd && rightArrayStart <= rightArrayEnd) {
if (nums[leftArrayStart] < nums[rightArrayStart]) {
tempNums[i] = nums[leftArrayStart];
leftArrayStart++;
} else {
tempNums[i] = nums[rightArrayStart];
rightArrayStart++;
}
i++;
}
while (leftArrayStart <= leftArrayEnd) {
tempNums[i] = nums[leftArrayStart];
leftArrayStart++;
i++;
}
while (rightArrayStart <= rightArrayEnd) {
tempNums[i] = nums[rightArrayStart];
rightArrayStart++;
i++;
}
for (int j = 0; j < tempNums.length; j++) {
nums[start + j] = tempNums[j];
}
return result;
} 本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-493-reverse-pairs翻转对思路分析及源码分享/
《LEETCODE 493. Reverse Pairs翻转对思路分析及源码分享》有1条回应