BiruLyu
7/24/2017 - 9:09 PM

## 493. Reverse Pairs(#).java

``````public class Solution {

class TreeNode{
long val;
int dup;
int count;
TreeNode left;
TreeNode right;
TreeNode(long v){
left = null;
right = null;
val = v;
dup = 1;
count = 0;
}
}

private void insert(TreeNode root, long val){
while(true){
if(root.val<val){
root.count++;
if(root.right==null) {
root.right = new TreeNode(val);
return;
}else{
root = root.right;
}
}else if(root.val==val){
root.dup++;
return;
}else{
if(root.left==null){
root.left = new TreeNode(val);
return;
}else{
root = root.left;
}
}
}
}

private int search(TreeNode root, long target){
if(root==null) return 0;
//        System.out.println(root.val+" "+target);
if(target<root.val) return root.count+root.dup+search(root.left,target);
else if(target==root.val) return root.count+search(root.left,target);
return search(root.right,target);
}

public int reversePairs(int[] nums) {
TreeNode root = new TreeNode(Integer.MIN_VALUE);
int ret = 0;
for(int x:nums) {
ret+=search(root.right,(long)2*x);
insert(root,(long)x);
}
return ret;
}
}``````
``````public class Solution {

int[] sorted;
private int[] merge(int[] nums, int s1, int e1, int s2, int e2){
int[] ret = new int[e1-s1+1+e2-s2+1];
int a = s1;
int b = s2;
int ind = 0;
while(a<=e1 || b<=e2){
if(a==e1+1){
while(b<=e2) ret[ind++] = nums[b++];
break;
}
if(b==e2+1){
while(a<=e1) ret[ind++] = nums[a++];
break;
}
if(nums[a]<nums[b]){
ret[ind++] = nums[a++];
}else ret[ind++] = nums[b++];
}
return ret;
}

private int mergeSort(int[] num, int start, int end){
if(start==end){
sorted[start] = num[start];
return 0;
}
if(start==end-1){
sorted[start] = Math.min(num[start],num[end]);
sorted[end] = Math.max(num[start],num[end]);
if((long)num[start]>(long)num[end]*2) return 1;
return 0;
}
int mid = (end-start)/2+start;
int ret = mergeSort(num,start,mid)+mergeSort(num,mid+1,end);
int left = start;
int right = mid+1;
while(left<=mid && right<=end){
if((long)sorted[left]>(long)2*sorted[right]){
ret+=mid-left+1;
//                System.out.println(left+" "+sorted[left]+" "+right+" "+sorted[right]);
right++;
}else left++;
}

int[] tmp = merge(sorted,start,mid,mid+1,end);
int ind = start;
for(int x:tmp) sorted[start++] = x;
return ret;
}

public int reversePairs(int[] nums) {
if(nums.length==0) return 0;
sorted = new int[nums.length];
return mergeSort(nums,0,nums.length-1);
}
}``````
``````public class Solution {
public int reversePairs(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] helper = new int[nums.length];
return countWhileMergeSort(nums, helper, 0, nums.length - 1);
}

private int countWhileMergeSort(int[] nums, int[] helper, int left, int right) {
if (left >= right) {
return 0;
}
int mid = left + (right - left) / 2;
int leftCount = countWhileMergeSort(nums, helper, left, mid);
int rightCount = countWhileMergeSort(nums, helper, mid + 1, right);
int i = left, j = mid + 1;
int count = leftCount + rightCount;
while (i <= mid && j <= right) {
if (nums[i] > 2L * nums[j]) {
count += mid + 1 - i;  // !!!!! based on the sorted array property
j++;
} else {
i++;
}
}

// merge
for (i = left; i <= right; i++) {
helper[i] = nums[i];
}
i = left;
j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (helper[i] <= helper[j]) {
nums[k++] = helper[i++];
} else {
nums[k++] = helper[j++];
}
}
while (i <= mid) {
nums[k++] = helper[i++];
}
// System.out.println(Arrays.toString(nums));
// System.out.printf("[%d, %d], count=%d\n", left, right, count);
return count;
}
}``````
``````public class Solution {
public int reversePairs(int[] nums) {
return mergeSort(nums, 0, nums.length-1);
}
private int mergeSort(int[] nums, int s, int e){
if(s>=e) return 0;
int mid = s + (e-s)/2;
int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e);
for(int i = s, j = mid+1; i<=mid; i++){
while(j<=e && nums[i]/2.0 > nums[j]) j++;
cnt += j-(mid+1);
}
Arrays.sort(nums, s, e+1);
return cnt;
}
}``````