分治-归并系列一＞翻转对

题目：

链接: link

---

这题和逆序对区别点就是，要找到前一个元素是后一个元素的2倍
先找到目标值再，继续堆排序

解析：

策略一：

代码：

class Solution {int[] tmp;public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return mergesort(nums,0,n-1);}private int mergesort(int[] nums, int left, int right){int ret = 0;if(left >= right) return 0;int mid = (right + left) / 2;//左右两边找翻转对ret += mergesort(nums,left,mid);ret += mergesort(nums,mid+1,right);//一左一右找翻转对: 降序版本//输入数组中的所有数字都在32位整数的表示范围内:改为：2.0*nums[cur2]int cur1 = left, cur2 = mid+1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= 2.0*nums[cur2]){cur2++;}else {ret += right - cur2 + 1;cur1++;}if(cur2 > right) break;}//排序：cur1 = left; cur2 = mid+1;while(cur1 <= mid && cur2 <= right) tmp[i++] = nums[cur1] <= nums[cur2]? nums[cur2++] : nums[cur1++];while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//放回原数组：for(int j = left; j <= right; j++){nums[j] = tmp[j-left];}return ret;}
}

策略二：

代码：

class Solution {int[] tmp;public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return mergesort(nums,0,n-1);}一左一右找翻转对: 升序版本:private int mergesort(int[] nums, int left, int right){int ret = 0;if(left >= right) return 0;int mid = (right + left) / 2;//左右两边找翻转对ret += mergesort(nums,left,mid);ret += mergesort(nums,mid+1,right);//一左一右找翻转对: 升序版本//输入数组中的所有数字都在32位整数的表示范围内:改为：2.0*nums[cur2]int cur1 = left, cur2 = mid+1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] / 2.0 <= nums[cur2]){cur1++;}else {ret += mid - cur1 + 1;cur2++;}if(cur1 > mid) break;}//排序：cur1 = left; cur2 = mid+1;while(cur1 <= mid && cur2 <= right) tmp[i++] = nums[cur1] <= nums[cur2]? nums[cur1++] : nums[cur2++];while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//放回原数组：for(int j = left; j <= right; j++){nums[j] = tmp[j-left];}return ret;}
}