493.reverse-pairs

发表评论
362 views

 ›
493.reverse-pairs

493. 翻转对

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

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

示例 1:

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

示例 2:

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

注意:

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

思路

  1. 暴力法：两个嵌套循环 O(n^2)
  2. merge-sort
  3. 树状数组

解法一

树状数组

解法二

归并排序

class Solution {
    public int helper(int[] nums, int begin, int end) {
        if (begin >= end) return 0;
        int mid = (begin+end) >>> 1;

        int res = helper(nums, begin, mid) + helper(nums, mid + 1, end);
        Arrays.sort(nums, begin, mid+1);
        Arrays.sort(nums, mid+1, end+1);

        int i = begin;
        int j = mid + 1;
        while(i <= mid && j <= end) {
            if (nums[i] > 2 * nums[j]) {
                res += mid - i + 1;
                j++;
            } else {
                i++;
            }
        }
        return res;
    }
    public int reversePairs(int[] nums) {
        int n = nums.length;
        return helper(nums, 0, n - 1);
    }
}

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;
    }
}

class Solution {
    public int ret = 0;
    public int reversePairs(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return ret;
    }

    private void mergeSort(int[] nums, int left, int right) {
       if (right <= left) return;
       int mid = (left + right) >>> 1;
       mergeSort(nums, left, mid);
       mergeSort(nums, mid + 1, right);

       int count = 0;
       for (int l = left, r = mid + 1; l <= mid;) {
           if (r > right || (long)nums[l] <= 2*(long)nums[r]) {
               l++;
               ret += count;
           } else {
               r++;
               count++;
           }
       }

       Arrays.sort(nums, left, right + 1);
    }
}

public class Solution {
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        return mergeSort(nums, 0, nums.length - 1);
    }
    private int mergeSort(int[] nums, int l, int r) {
        if (l >= r) return 0;
        int mid = l + (r - l)/2;
        int count = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r);
        int[] cache = new int[r - l + 1];
        int i = l, t = l, c = 0;
        for (int j = mid + 1; j <= r; j++, c++) {
            while (i <= mid && nums[i] <= 2 * (long)nums[j]) i++;
            while (t <= mid && nums[t] < nums[j]) cache[c++] = nums[t++];
            cache[c] = nums[j];
            count += mid - i + 1;
        }
        while (t <= mid) cache[c++] = nums[t++];
        System.arraycopy(cache, 0, nums, l, r - l + 1);
        return count;
    }
}