題目：

鏈接: 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;}
}