LeetCode-493翻转对-困难

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

输入: [1,3,2,3,1]
输出: 2

输入: [2,4,3,5,1]
输出: 3

给定数组的长度不会超过50000。输入数组中的所有数字都在32位整数的表示范围内。

// 我的存在问题
public int reversePairs(int[] nums) {
    if (nums.length < 2 || nums == null) {
        return 0;
    }
    int ans = process(nums, 0, nums.length - 1);
    return ans;
}

public int process(int[] arr, int left, int right) {
    if (left == right) {
        return 0;
    }
    int mid = left + ((right - left) >> 1);
    return
            process(arr, left, mid)
                    + process(arr, mid + 1, right)
                    + merge(arr, left, mid, right);
}

public int merge(int[] arr, int left, int mid, int right) {
    int p1 = left;
    int p2 = mid + 1;
    int i = 0;
    int[] temp = new int[right - left + 1];
    // 排序
    int sum = 0;
    int t = 0;
    boolean flag = false;
    while (p1 <= mid && p2 <= right) {
        if ((long) arr[p1] > (long) arr[p2] * 2) { // 防止比较越界
            sum += mid - p1 + 1;
            temp[i++] = arr[p2++];
            if (flag == true) {
                p1 = t;
                flag = false;
            }
        } else if (arr[p1] > arr[p2]) {
            if (flag == false){
                t = p1;
                flag = true;
            }
            p1 ++;
        } else {
            temp[i++] = arr[p1++];
        }
    }
    if (flag && p1 > mid) {
        while (t <= mid && p2 <= right) {
            temp[i++] = arr[t] <= arr[p2] ? arr[t++] : arr[p2++];
        }
        while (t <= mid) {
            temp[i++] = arr[t++];
        }
    }
    while (p1 <= mid) {
        temp[i++] = arr[p1++];
    }
    while (p2 <= right) {
        temp[i++] = arr[p2++];
    }
    // 回归给arr
    for (int j = 0; j < temp.length; j++) {
        arr[left + j] = temp[j];
    }
    return sum;
}

// 我的解决方法：先计数再排序
public int reversePairs(int[] nums) {
    if (nums.length < 2 || nums == null) {
        return 0;
    }
    int ans = process(nums, 0, nums.length - 1);
    return ans;
}

public int process(int[] arr, int left, int right) {
    if (left == right) {
        return 0;
    }
    int mid = left + ((right - left) >> 1);
    return
            process(arr, left, mid)
                    + process(arr, mid + 1, right)
                    + merge(arr, left, mid, right);
}

public int merge(int[] arr, int left, int mid, int right) {
    int p1 = left;
    int p2 = mid + 1;
    int[] temp = new int[right - left + 1];
    // 排序
    int sum = 0;
    boolean flag = false;
    // 先统计
    while (p1 <= mid && p2 <= right) {
        if ((long) arr[p1] > (long) arr[p2] * 2) {
            sum += mid - p1 + 1;
            p2 ++;
        } else {
            p1 ++;
        }
    }
    // 排序
    p1 = left;
    p2 = mid + 1;
    int i = 0;
    while (p1 <= mid && p2 <= right) {
        temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= mid) {
        temp[i++] = arr[p1++];
    }
    while (p2 <= right) {
        temp[i++] = arr[p2++];
    }
    // 回归给arr
    for (int j = 0; j < temp.length; j++) {
        arr[left + j] = temp[j];
    }
    return sum;
}

// 以下是官方答案
public int reversePairs2(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    return reversePairsRecursive(nums, 0, nums.length - 1);
}

public int reversePairsRecursive(int[] nums, int left, int right) {
    if (left == right) {
        return 0;
    } else {
        int mid = (left + right) / 2;
        int n1 = reversePairsRecursive(nums, left, mid);
        int n2 = reversePairsRecursive(nums, mid + 1, right);
        int ret = n1 + n2;

        // 首先统计下标对的数量
        int i = left;
        int j = mid + 1;
        while (i <= mid) {
            while (j <= right && (long) nums[i] > 2 * (long) nums[j]) {
                j++;
            }
            ret += j - mid - 1;
            i++;
        }

        // 随后合并两个排序数组
        int[] sorted = new int[right - left + 1];
        int p1 = left, p2 = mid + 1;
        int p = 0;
        while (p1 <= mid || p2 <= right) {
            if (p1 > mid) {
                sorted[p++] = nums[p2++];
            } else if (p2 > right) {
                sorted[p++] = nums[p1++];
            } else {
                if (nums[p1] < nums[p2]) {
                    sorted[p++] = nums[p1++];
                } else {
                    sorted[p++] = nums[p2++];
                }
            }
        }
        for (int k = 0; k < sorted.length; k++) {
            nums[left + k] = sorted[k];
        }
        return ret;
    }
}