[Leetcode] 分治

satjd

2018/11/03

Categories: Algorithm 基础知识 Tags: leetcode

493. Reverse Pairs

class Solution {
    // 分治法 时间复杂度O(nlogn)
    public int reversePairs(int[] nums) {
        return mergeForCnt(nums,0,nums.length-1);
    }
    
    // 类似归并排序的扫描方式,用来统计符合要求的pair
    private int mergeForCnt(int[] nums, int left, int right) {
        if (right <= left) {
            return 0;
        }
        
        int mid = left + (right - left) / 2;
        int ret = 0;
        
        ret += mergeForCnt(nums,left, mid);
        ret += mergeForCnt(nums,mid+1, right);
        
        int i = left, j = mid+1, cnt = 0, jlast = 0;
        while (i <= mid && j <= right) {
           if ((long)nums[i] <= (long)nums[j]*2) {
               i++;
               ret += cnt;
            } else {
               jlast = nums[j];
               j++;
               cnt++;
            } 
        }
        if (j > right) {
            ret += cnt * (mid - i + 1);
        }
        
        // 上面的扫描方式需要数组有序(否则会漏掉一部分pair)
        // 这里需要对扫描过的数组排序
        merge(nums,left,mid,right);
        
        return ret;
    }
    
    
    private void merge(int[] nums, int left, int mid, int right) {
        int[] helper = new int[right - left + 1];
        int i = left, j = mid+1, tail = 0;
        while (i <= mid && j <= right) {
            if (nums[i] < nums[j]) {
                helper[tail++] = nums[i];
                i++;
            } else {
                helper[tail++] = nums[j];
                j++;
            }
        }
        while (i <= mid) {
            helper[tail++] = nums[i];
            i++;
        }
        while (j <= right) {
            helper[tail++] = nums[j];
            j++;
        }
        
        int k = left;
        for(int m : helper) {
            nums[k++] = m;
        }
    }
}