493. Reverse Pairs(BST, BIT, MergeSort)

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: Brute Force.

class Solution {

public:

    int reversePairs(vector<int>& nums) {

        int len = nums.size();

        int count = 0;

        for (int i = 0; i < len; ++i) {

            for (int j = i + 1; j < len; ++j) {

                if (nums[i] > nums[j] * 2LL) count++;

            }

        }

        return count;

    }

};

Approach #2: Binary Search Tree.

class Node {

public:

    int val, count_ge;

    Node *left, *right;

    Node(int val) {

        this->val = val;

        this->count_ge = 1;

        this->left = NULL;

        this->right = NULL;

    }

};

class Solution {

public:

    int reversePairs(vector<int>& nums) {

        int len = nums.size();

        int count = 0;

        Node* head = NULL;

        for (int i = 0; i < len; ++i) {

            count += search(head, nums[i] * 2LL + 1);

            head = insert(head, nums[i]);

        }

        return count;

    }

private:

    int search(Node* head, long long val) {

        if (head == NULL)

            return 0;

        else if (head->val == val) {

            return head->count_ge;

        } else if (head->val > val) {

            return head->count_ge + search(head->left, val);

        } else {

            return search(head->right, val);

        }

    }

    Node* insert(Node* head, int val) {

        if (head == NULL) return new Node(val);

        else if (head->val == val)

            head->count_ge++;

        else if (head->val < val) {

            head->count_ge++;

            head->right = insert(head->right, val);

        } else {

            head->left = insert(head->left, val);

        }

        return head;

    }

};

Approach #3: Binary Index Tree.

class Solution {

    public int reversePairs(int[] nums) {

        if (nums == null || nums.length <= 1) return 0;

        int n = nums.length;

        int[] nums_copy = nums.clone();

        Arrays.sort(nums_copy);

        int[] BITS = new int[n+1];

        int count = 0;

        for (int i = n-1; i >= 0; --i) {

            count += query(BITS, index(nums_copy, 1.0 * nums[i] / 2));

            update(BITS, index(nums_copy, nums[i]));

        }

        return count;

    }

    private void update(int[] BIT, int index) {

        index = index + 1;

        while (index < BIT.length) {

            BIT[index]++;

            index += index & (-index);

        }

    }

    private int query(int[] BIT, int index) {

        int sum = 0;

        while (index > 0) {

            sum += BIT[index];

            index -= index & (-index);

        }

        return sum;

    }

    private int index(int[] arr, double val) {

        int lo = 0, hi = arr.length;

        while (lo < hi) {

            int mid = lo + (hi - lo) / 2;

            if (arr[mid] >= val) hi = mid;

            else lo = mid + 1;

        }

        return lo;

    }

}

Approach #4: Mergesort.

class Solution(object):

    def __init__(self):

        self.cnt = 0

    def reversePairs(self, nums):

        """

        :type nums: List[int]

        :rtype: int

        """

        def msort(lst):

            L = len(lst)

            if L <= 1:

                return lst

            else:

                return merge(msort(lst[:int(L/2)]), msort(lst[int(L/2):]))

        def merge(left, right):

            l, r = 0, 0

            while l < len(left) and r < len(right):

                if left[l] <= 2*right[r]:

                    l += 1

                else:

                    self.cnt += len(left)-l

                    r += 1

            return sorted(left+right)

        msort(nums)

        return self.cnt

巴特西

493. Reverse Pairs(BST, BIT, MergeSort)

最新文章

热门文章