493.Reverse-Pairs

493. Reverse Pairs

้ข˜็›ฎๅœฐๅ€

https://leetcode.com/problems/reverse-pairs/

https://lotabout.me/2018/binary-indexed-tree/

้ข˜็›ฎๆ่ฟฐ

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:
Input: [1,3,2,3,1]
Output: 2

Example2:
Input: [2,4,3,5,1]
Output: 3

Note:
The length of the given array will not exceed 50,000.
All the numbers in the input array are in the range of 32-bit integer.

ไปฃ็ 

Approach #1 Merge Sort

class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;

        if (nums == null || n == 0)     return 0;

        return mergeSort(nums, 0, n - 1);
    }

    private int mergeSort(int[] nums, int start, int end) {
        if (start >= end)   return 0;

        int mid = start + (end - start) / 2;
        int res = mergeSort(nums, start, mid) + mergeSort(nums, mid+1, end);

        int j = mid + 1;
        for (int i = start; i <= mid; i++) {
            while (j <= end && nums[i] / 2.0 > nums[j]) { // ้˜ฒๆญขๆบขๅ‡บ
                j++;
            }
            res += j - (mid + 1);
        }

        Arrays.sort(nums, start, end + 1);
        return res;
    }
}

Approach #2 BIT

class Solution {
    public int reversePairs(int[] nums) {
       int[] nums_copy = Arrays.copyOf(nums, nums.length);
        Arrays.sort(nums_copy);
        int[] bit = new int[nums_copy.length + 1];

        int cnt = 0;
        for (int num: nums) {
              // ๅˆฉ็”จBITๆ•ฐๆฎ็ป“ๆž„็ปŸ่ฎกๅคงไบŽ2*num็š„ๅ…ƒ็ด ไธชๆ•ฐ
            cnt += query(bit, index(nums_copy, num * 2L + 1));
             // ๆ’ๅ…ฅๅฝ“ๅ‰ๅ…ƒ็ด ๏ผŒ่ฟ™้‡Œindexๆ˜ฏnumๅœจcopyไธญ็š„ไธ‹ๆ ‡
            insert(bit, index(nums_copy, num));
        }

        return cnt;
    }

    // ่ฟ”ๅ›žๅคงไบŽๆˆ–่€…็ญ‰ไบŽtarget็š„ๅๆ ‡๏ผŒๅฆ‚ๆžœๅคšไธชtarget่ฟ”ๅ›ž็ฌฌไธ€ไธชๅๆ ‡
    private int index(int[] nums, long target) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] >= target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        // bitๆ•ฐ็ป„ๆ˜ฏไปฅ1ไธบๅผ€ๅง‹๏ผŒๆ‰€ไปฅ่ฟ”ๅ›žstart+1
        return start + 1;
    }

    private void insert(int[] bit, int i) {
        while (i > 0) {
            bit[i] ++;  // ๆฏ”bit[i]ๅคง็š„ไธชๆ•ฐ
            i -= i & -i;
        }
    }

    private int query(int[] bit, int i) {
        int sum = 0;
        while (i < bit.length) {
            sum += bit[i];
            i += i & -i;
        }
        return sum;
    }
}

Approach #3 BST

ๅฏๆƒœ็š„ๆ˜ฏ๏ผŒๆˆ‘ไปฌ่‡ชๅฎšไน‰็š„ๆ ‘ๅนถไธๆ˜ฏไธ€ไธชๅนณ่กกไบŒๅ‰ๆ ‘๏ผŒๅœจๆœ€ๅ็š„ๆƒ…ๅ†ตไธ‹ไผšๅฏผ่‡ด้•ฟ้“พ่กจ๏ผŒๅฆ‚ๆžœLeetCodeไธŠไฝฟ็”จไธŠ่ฟฐไปฃ็ ไผšๅฏผ่‡ดTLE(Time Limit Exceeded)ใ€‚

public class Solution {
    public int reversePairs(int[] nums) {
        Node root = null;
        int[] cnt = new int[1];
        for (int i = nums.length-1; i>=0; i--) {
            search(cnt, root, nums[i]/2.0);//search and count the partially built tree
            root = build(nums[i], root);//add nums[i] to BST
        }
        return cnt[0];
    }

    private void search(int[] cnt, Node node, double target){
        if (node == null) return; 
        else if(target == node.val) cnt[0] += node.less;
        else if(target < node.val) search(cnt, node.left, target);
        else {
            cnt[0] += node.less + node.same; 
            search(cnt, node.right, target);
        }
    }

    private Node build(int val, Node n) {
        if (n == null) return new Node(val);
        else if (val == n.val) n.same+=1;
        else if (val > n.val) n.right = build(val, n.right);
        else {
            n.less += 1;
            n.left = build(val, n.left);
        }
        return n;
    }

    class Node{
        int val, less = 0, same = 1;//less: number of nodes that less than this node.val
        Node left, right;
        public Node(int v){
            this.val = v;
        }
    }
}

Last updated