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:
50,000.
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)
原文：https://www.cnblogs.com/ruruozhenhao/p/10046929.html