TODO https://leetcode.com/problems/reverse-pairs/discuss/97268/General-principles-behind-problems-similar-to-%22Reverse-Pairs%22
https://leetcode.com/problems/reverse-pairs/
X. BST
https://discuss.leetcode.com/topic/78933/very-short-and-clear-mergesort-bst-java-solutions
https://discuss.leetcode.com/topic/78933/very-short-and-clear-java-solution-using-bst
Build the Binary Search Tree from right to left, and at the same time, search the partially built tree with nums[i]/2.0
X. Merge Sort
http://www.cnblogs.com/grandyang/p/6657956.html
fun4LeetCode大神归纳的第二种方法叫做分割重现关系(Partition Recurrence Relation)，用式子表示是T(i, j) = T(i, m) + T(m+1, j) + C。这里的C就是处理合并两个部分的子问题，那么用文字来描述就是“已知翻转对的两个数字分别在子数组nums[i, m]和nums[m+1, j]之中，求满足要求的翻转对的个数”，这里翻转对的两个条件中的顺序条件已经满足，就只需要找到满足大小关系的的数对即可。这里两个数字都是不确定的，如果用暴力搜索肯定会被OJ唾弃。但是如果两个子数组是有序的，那么我们可以用双指针的方法在线性时间内就可以统计出符合题意的翻转对的个数。要想办法产生有序的子数组，那么这就和MergeSort的核心思想完美匹配了。我们知道混合排序就是不断的将数组对半拆分成子数组，拆到最小的数组后开始排序，然后一层一层的返回，最后原数组也是有序的了。这里我们在混合排序的递归函数中，对于有序的两个子数组进行统计翻转对的个数，然后再逐层返回，这就完美的实现了上述的分割重现关系的思想。
https://discuss.leetcode.com/topic/79066/20-lines-java-code-beats-100
https://discuss.leetcode.com/topic/78950/java-merge-sort-solution-o-nlog-n
https://www.acwing.com/solution/leetcode/content/396/
首先将 nums 中的数字和每个数字的 2 倍统一进行离散化到 [1, 2n]。
接下来仿照求逆序对的思路，从数组最后开始往前遍历，遍历过程中，在树状数组中查找小于等于 nums[i] 离散化后的值 x 再减 1 的个数。然后将 nums[i]*2 离散化后的值加入到树状数组中。
时间复杂度
离散化的时间复杂度为 O(nlogn)O(nlogn)，树状数组每次操作的时间复杂度为 O(logn)O(logn)，故总时间复杂度为 O(nlogn)O(nlogn)。
http://www.cnblogs.com/grandyang/p/6657956.html
https://leetcode.com/problems/reverse-pairs/discuss/97268/General-principles-behind-problems-similar-to-%22Reverse-Pairs%22
树状数组Binary Indexed Tree不光可以用于求和，还可以求频率。
http://bookshadow.com/weblog/2017/02/12/leetcode-reverse-pairs/
http://blog.csdn.net/kakitgogogo/article/details/55097648
这道题一看就是二分查找的典型题，再用一个同样大的数组保存元素2*nums的值，然后对这个数组排序。剩下的操作都是显而易见了，全是二分查找的基本操作
LintCode - Reverse Pairs
http://www.jiuzhang.com/solutions/reverse-pairs/
X. Segment tree
https://leetcode.com/problems/reverse-pairs/discuss/97310/Java-Segment-Tree-Solution
https://leetcode.com/problems/reverse-pairs/discuss/171765/O(N*log(MAXN)-)Sparse-segment-tree-solution-getting-TLE.
https://leetcode.com/problems/reverse-pairs/
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.
X. BST
https://discuss.leetcode.com/topic/78933/very-short-and-clear-mergesort-bst-java-solutions
BST solution is no longer acceptable, because it's performance can be very bad, O(n^2), for extreme cases, due to the its unbalance, but I am still providing it below just FYI.
We build the Binary Search Tree from right to left, and at the same time, search the partially built tree with nums[i]/2.0. The code below should be clear enough.
We build the Binary Search Tree from right to left, and at the same time, search the partially built tree with nums[i]/2.0. The code below should be clear enough.
Build the Binary Search Tree from right to left, and at the same time, search the partially built tree with nums[i]/2.0
X. Merge Sort
http://www.cnblogs.com/grandyang/p/6657956.html
fun4LeetCode大神归纳的第二种方法叫做分割重现关系(Partition Recurrence Relation)，用式子表示是T(i, j) = T(i, m) + T(m+1, j) + C。这里的C就是处理合并两个部分的子问题，那么用文字来描述就是“已知翻转对的两个数字分别在子数组nums[i, m]和nums[m+1, j]之中，求满足要求的翻转对的个数”，这里翻转对的两个条件中的顺序条件已经满足，就只需要找到满足大小关系的的数对即可。这里两个数字都是不确定的，如果用暴力搜索肯定会被OJ唾弃。但是如果两个子数组是有序的，那么我们可以用双指针的方法在线性时间内就可以统计出符合题意的翻转对的个数。要想办法产生有序的子数组，那么这就和MergeSort的核心思想完美匹配了。我们知道混合排序就是不断的将数组对半拆分成子数组，拆到最小的数组后开始排序，然后一层一层的返回，最后原数组也是有序的了。这里我们在混合排序的递归函数中，对于有序的两个子数组进行统计翻转对的个数，然后再逐层返回，这就完美的实现了上述的分割重现关系的思想。
https://discuss.leetcode.com/topic/79066/20-lines-java-code-beats-100
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;
}
Explanation: In each round, we divide our array into two parts and sort them. So after "int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e); ", the left part and the right part are sorted and now our only job is to count how many pairs of number (leftPart[i], rightPart[j]) satisfies leftPart[i] <= 2*rightPart[j].
For example,
left: 4 6 8 right: 1 2 3
so we use two pointers to travel left and right parts. For each leftPart[i], if j<=e && nums[i]/2.0 > nums[j], we just continue to move j to the end, to increase rightPart[j], until it is valid. Like in our example, left's 4 can match 1 and 2; left's 6 can match 1, 2, 3, and left's 8 can match 1, 2, 3. So in this particular round, there are 8 pairs found, so we increases our total by 8.
For example,
left: 4 6 8 right: 1 2 3
so we use two pointers to travel left and right parts. For each leftPart[i], if j<=e && nums[i]/2.0 > nums[j], we just continue to move j to the end, to increase rightPart[j], until it is valid. Like in our example, left's 4 can match 1 and 2; left's 6 can match 1, 2, 3, and left's 8 can match 1, 2, 3. So in this particular round, there are 8 pairs found, so we increases our total by 8.
Clearer and simpler version, but slower, got the idea by another 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;
}
Because left part and right part are sorted, you can replace the Arrays.sort() part with a actual merge sort process. The previous version is easy to write, while this one is faster.
int[] helper;
public int reversePairs(int[] nums) {
this.helper = new int[nums.length];
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);
myMerge(nums, s, mid, e);
return cnt;
}
private void myMerge(int[] nums, int s, int mid, int e){
for(int i = s; i<=e; i++) helper[i] = nums[i];
int p1 = s;//pointer for left part
int p2 = mid+1;//pointer for rigth part
int i = s;//pointer for sorted array
while(p1<=mid || p2<=e){
if(p1>mid || (p2<=e && helper[p1] >= helper[p2])){
nums[i++] = helper[p2++];
}else{
nums[i++] = helper[p1++];
}
}
}https://discuss.leetcode.com/topic/78950/java-merge-sort-solution-o-nlog-n
public int ret;
public int reversePairs(int[] nums) {
ret = 0;
mergeSort(nums, 0, nums.length-1);
return ret;
}
public void mergeSort(int[] nums, int left, int right) {
if (right <= left) {
return;
}
int middle = left + (right - left)/2;
mergeSort(nums, left, middle);
mergeSort(nums,middle+1, right);
//count elements
int count = 0;
for (int l = left, r = middle+1; l <= middle;) {
if (r > right || (long)nums[l] <= 2*(long)nums[r]) {
l++;
ret += count;
} else {
r++;
count++;
}
}
//merge sort
int[] temp = new int[right - left + 1];
for (int l = left, r = middle+1, k = 0; l <= middle || r <= right;) {
if (l <= middle && ((r > right) || nums[l] < nums[r])) {
temp[k++] = nums[l++];
} else {
temp[k++] = nums[r++];
}
}
for (int i = 0; i < temp.length; i++) {
nums[left + i] = temp[i];
}
}https://www.acwing.com/solution/leetcode/content/396/
首先将 nums 中的数字和每个数字的 2 倍统一进行离散化到 [1, 2n]。
接下来仿照求逆序对的思路，从数组最后开始往前遍历，遍历过程中，在树状数组中查找小于等于 nums[i] 离散化后的值 x 再减 1 的个数。然后将 nums[i]*2 离散化后的值加入到树状数组中。
时间复杂度
离散化的时间复杂度为 O(nlogn)O(nlogn)，树状数组每次操作的时间复杂度为 O(logn)O(logn)，故总时间复杂度为 O(nlogn)O(nlogn)。
http://www.cnblogs.com/grandyang/p/6657956.html
对于这类数组找数字之间的关系的题，一种很好的解题思路就是拆分数组来解决子问题，就是把大问题拆成小问题，把小问题一一解决来，大问题的答案也就出来了，这么说起来是不是有点像DP的感觉，但是不同的是，博主感觉此类问题很难找到DP的递推公式吧。fun4LeetCode大神归纳了两种拆分方法，一种叫顺序重现关系(Sequential Recurrence Relation)，用式子表示是T(i, j) = T(i, j - 1) + C。这里的C就是处理最后一个数字的子问题，那么用文字来描述就是“已知翻转对的第二个数字为nums[j], 在子数组nums[i, j - 1]中找翻转对的第一个数字”，这里翻转对的两个条件中的顺序条件已经满足，就只需要找比2*nums[j]大的数即可。当然最森破的方法就是线性扫描，但这样整个时间复杂度就会上升到令人发指的O(n2)，这又怎么能逃过连Binary Search都不放过的OJ的魔爪。由于二分搜索和BST等方法已经被OJ阉割，所以我们只能用树状数组Binary Indexed Tree来做了。关于BIT，我之前有篇博客Range Sum Query - Mutable 应该讲的比较清楚了，如果弄懂了那篇博客，我们对BIT的机制也应该有个基本的了解，由于BIT的存储方式不是将数组中的数字对应的一一存入，而是有的对应存入，有的是存若干个数字之和，其设计初衷之一就是要在O(lgn)的时间复杂度下完成求和运算。那么我们该如何利用这一特性呢，这跟这道题又有什么关系呢，别着急，博主会慢慢解释。
首先我们应该确定一个遍历的方向，这里博主推荐从后往前遍历数组，这样做的好处是对于当前遍历到的数字，在已遍历过的数字中找小于当前数字的一半(nums[i]/2.0)的数字，这样的遍历方向也能跟上面的顺序重现关系的定义式统一起来。当然如果你想强行从前往后遍历，也不是不行，那么就需要在已遍历的数字中找大于当前数字的二倍(nums[i]*2)的数字就行了。由于我们要在之前遍历过的数字中找符合条件的数字，怎么样利用BIT的特性来快速的找到是这种解法的最大难点。我们需要将之前遍历过的数字存入BIT中，怎么存是难点。由于之前那篇博客我们知道BIT用update函数来存数，需要提供要存入的位置和要存入的数字这两个参数，那么这里难道我们就按照数字在原数组中的位置存入BIT吗，这样做毫无意义！我们要存的是该数字在有序数组中的位置，而且存入的也不是该数字本身，而是该数字出现的次数1。我们用题目中的第一个例子来说明，我们先给数组排序，得到：
1 1 2 3 3
对于每一个数字我们要确定其在BIT中的位置，由于有重复数字的存在，那么每个数字对应的位置就是其最后出现的位置，而且因为BIT是从1开始的，并不是像一般的数组那样从0开始，那么有如下对应关系：
1->2, 2->3, 3->5
那么当我们遇到数字1了，就update(2,1)，遇到数字2了，就update(3,1)，遇到数字3了，就update(5,1)。我们之前解释了并不把数字本身存入BIT，而是将其对应的位置存入BIT，真正存入的数字是1，这样方便累加，而且由于1是固定的，在下面的代码中就不用将1当作函数的参数了。这样我们知道了如果存入数字，那么我们在遍历到新数字时，为了得到符合要求的数字的个数，需利用BIT的getSum函数。getSum函数需要提供一个位置参数，可以返回该位置之前的所有数之和。同理，我们提供的参数既不是当前遍历到的数字本身，也不是其在原数组中的位置，而是该数字的一半(nums[i]/2.0)在有序数组中的正确位置，可以用lower_bound函数来找第一个不小于目标值的位置，当然我们也可以自己写个二分搜索的子函数来代替lower_bound函数。比如我们当前遍历到的数字是3，那么我们在有序数组中找1.5的位置，返回是2，此时我们在BIT中用getSum来返回位置2之前的数字之和，返回几就表示有几个小于1.5的数字。讲到这里基本上这种解法的核心内容都讲完了，如果你还是一头雾水，那么就是博主的表述能力的问题了(沮丧脸:()。那么博主只能建议你带实例一步一步去试，看看每一步操作后BIT中的结果是啥，下面就列出这些内容：
update(2,1) -> BIT: 0 0 1 0 1 0
update(5,1) -> BIT: 0 0 1 0 1 1
update(3,1) -> BIT: 0 0 1 1 2 1
update(5,1) -> BIT: 0 0 1 1 2 2
update(2,1) -> BIT: 0 0 2 1 3 2
int reversePairs(vector<int>& nums) { int res = 0, n = nums.size(); vector<int> v = nums, bit(n + 1); sort(v.begin(), v.end()); unordered_map<int, int> m; for (int i = 0; i < n; ++i) m[v[i]] = i + 1; for (int i = n - 1; i >= 0; --i) { res += getSum(lower_bound(v.begin(), v.end(), nums[i] / 2.0) - v.begin(), bit); update(m[nums[i]], bit); } return res; } int getSum(int i, vector<int>& bit) { int sum = 0; while (i > 0) { sum += bit[i]; i -= (i & -i); } return sum; } void update(int i, vector<int>& bit) { while (i < bit.size()) { bit[i] += 1; i += (i & -i); } }
I spend a lot of time to understand the BIT solutions, partially because of the reverse treatment of searching and updating, and I found by iterate the original array from the end, we can avoid such reverse meaning...
And the main program, where again we will search for all elements greater than twice of current element while insert the element itself into the BIT. For each element, the
"index" function will return its index in the BIT. Unlike the BST-based solution, this is guaranteed to run at O(nlogn).
public int reversePairs(int[] nums) {
if (nums == null || nums.length <= 1)
return 0;
int n = nums.length;
int[] BIT = new int[n + 1];
int[] copy = nums.clone();
Arrays.sort(copy);
int res = 0;
for (int i = n - 1; i >= 0; i--) {
// find the first position in the array, where copy[index] >= num / 2, then any
// rand before index will contribute to the result
int num = nums[i];
res += search(BIT, index(copy, 1.0 * num / 2));
insert(BIT, index(copy, num));
}
return res;
}
private int search(int[] BIT, int i) {
int cnt = 0;
while (i > 0) {
cnt += BIT[i];
i -= (i & -i);
}
return cnt;
}
private void insert(int[] BIT, int i) {
i = i + 1;
while (i < BIT.length) {
BIT[i]++;
i += (i & -i);
}
}
//first position that has num >= val
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;
}
public int reversePairs(int[] nums) {
int res = 0;
int[] copy = Arrays.copyOf(nums, nums.length);
int[] bit = new int[copy.length + 1];
Arrays.sort(copy);
for (int ele : nums) {
res += search(bit, index(copy, 2L * ele + 1));
insert(bit, index(copy, ele));
}
return res;
}
private int index(int[] arr, long val) {
int l = 0, r = arr.length - 1, m = 0;
while (l <= r) {
m = l + ((r - l) >> 1);
if (arr[m] >= val) {
r = m - 1;
} else {
l = m + 1;
}
}
return l + 1;
}
More explanation for the BIT-based solution:
- We want the elements to be sorted so there is a sorted version of the input array which is
copy. - The
bitis built upon this sorted array. Its length is one greater than that of thecopyarray to account for the root. - Initially the
bitis empty and we start doing a sequential scan of the input array. For each element being scanned, we first search thebitto find all elements greater than twice of it and add the result tores. We then insert the element itself into thebitfor future search. - Note that conventionally searching of the
bitinvolves traversing towards the root from some index of thebit, which will yield a predefined running total of thecopyarray up to the corresponding index. For insertion, the traversing direction will be opposite and go from some index towards the end of thebitarray. - For each scanned element of the input array, its searching index will be given by the index of the first element in the
copyarray that is greater than twice of it (shifted up by1to account for the root), while its insertion index will be the index of the first element in thecopyarray that is no less than itself (again shifted up by1). This is what theindexfunction is for. - For our case, the running total is simply the number of elements encountered during the traversal process. If we stick to the convention above, the running total will be the number of elements smaller than the one at the given index, since the
copyarray is sorted in ascending order. However, we'd actually like to find the number of elements greater than some value (i.e., twice of the element being scanned), therefore we need to flip the convention. This is what you see inside thesearchandinsertfunctions: the former traversing towards the end of thebitwhile the latter towards the root.
树状数组Binary Indexed Tree不光可以用于求和，还可以求频率。
class Solution {
private int search(int[] BITree, int i) {
int sum = 0;
while (i < BITree.length) {
sum = sum + BITree[i];
i = i + (i & -i);
}
return sum;
}
private void insert(int[] BITree, int i) {
while (i > 0) {
BITree[i] += 1;
i = i - (i & -i);
}
}
public int reversePairs(int[] nums) {
int res = 0;
int[] copy = Arrays.copyOf(nums, nums.length);
int[] BITree = new int[copy.length + 1];
Arrays.sort(copy);
for (int num : nums) {
// 先查找在之前的数字中，有多少个val大于等于nums[i] * 2l + 1的数字
res += search(BITree, index(copy, 2L * num + 1));
// 再插入该数字
insert(BITree, index(copy, num));
}
return res;
}
// 在一个有序数组中搜索
// For each element, the "index" function will return its index in the BIT.
// Unlike the BST-based solution, this is guaranteed to run at O(nlogn)
private int index(int[] arr, long val) {
int l = 0, r = arr.length - 1, m = 0;
while (l <= r) {
m = l + ((r - l) >> 1);
if (arr[m] >= val) {
r = m - 1;
} else {
l = m + 1;
}
}
return l + 1;
}
}
树状数组 （Binary Indexed Tree / Fenwick Tree）
https://leetcode.com/problems/reverse-pairs/discuss/97268/General-principles-behind-problems-similar-to-%22Reverse-Pairs%22
The fundamental idea is very simple: break down the array and solve for the subproblems.
A breakdown of an array naturally reminds us of subarrays. To smoothen our following discussion, let's assume the input array is
nums, with a total of n elements. Let nums[i, j] denote the subarray starting from index i to index j (both inclusive), T(i, j) as the same problem applied to this subarray (for example, for Reverse Pairs, T(i, j) will represent the total number of important reverse pairs for subarray nums[i, j]).
With the definition above, it's straightforward to identify our original problem as
T(0, n - 1). Now the key point is how to construct solutions to the original problem from its subproblems. This is essentially equivalent to building recurrence relations for T(i, j). Since if we can find solutions to T(i, j) from its subproblems, we surely can build solutions to larger subarrays until eventually the whole array is spanned.
While there may be many ways for establishing recurrence relations for
T(i, j), here I will only introduce the following two common ones:T(i, j) = T(i, j - 1) + C, i.e., elements will be processed sequentially andCdenotes the subproblem for processing the last element of subarraynums[i, j]. We will call this sequential recurrence relation.T(i, j) = T(i, m) + T(m + 1, j) + Cwherem = (i+j)/2, i.e., subarraynums[i, j]will be further partitioned into two parts andCdenotes the subproblem for combining the two parts. We will call this partition recurrence relation.
For either case, the nature of the subproblem
C will depend on the problem under consideration, and it will determine the overall time complexity of the original problem. So usually it's crucial to find efficient algorithm for solving this subproblem in order to have better time performance. Also pay attention to possibilities of overlapping subproblems, in which case a dynamic programming (DP) approach would be preferred.
Next, I will apply these two recurrence relations to this problem "Reverse Pairs" and list some solutions for your reference.
I -- Sequential recurrence relation
Again we assume the input array is
nums with n elements and T(i, j) denotes the total number of important reverse pairs for subarray nums[i, j]. For sequential recurrence relation, we can set i = 0, i.e., the subarray always starts from the beginning. Therefore we end up with:T(0, j) = T(0, j - 1) + C
where the subproblem
C now becomes "find the number of important reverse pairs with the first element of the pair coming from subarray nums[i, j - 1] while the second element of the pair being nums[j]".
Note that for a pair
(p, q) to be an important reverse pair, it has to satisfy the following two conditions:p < q: the first element must come before the second element;nums[p] > 2 * nums[q]: the first element has to be greater than twice of the second element.
For subproblem
C, the first condition is met automatically; so we only need to consider the second condition, which is equivalent to searching for all elements within subarray nums[i, j - 1] that are greater than twice of nums[j].
The straightforward way of searching would be a linear scan of the subarray, which runs at the order of
O(j). From the sequential recurrence relation, this leads to the naive O(n^2) solution.
To improve the searching efficiency, a key observation is that the order of elements in the subarray does not matter, since we are only interested in the total number of important reverse pairs. This suggests we may sort those elements and do a binary search instead of a plain linear scan.
If the searching space (formed by elements over which the search will be done) is "static" (it does not vary from run to run), placing the elements into an array would be perfect for us to do the binary search. However, this is not the case here. After the
j-th element is processed, we need to add it to the searching space so that it becomes searchable for later elements, which renders the searching space expanding as more and more elements are processed.
Therefore we'd like to strike a balance between searching and insertion operations. This is where data structures like binary search tree (
BST) or binary indexed tree (BIT) prevail, which offers relatively fast performance for both operations.
1.
BST-based solution
we will define the tree node as follows, where
val is the node value and cnt is the total number of elements in the subtree rooted at current node that are greater than or equal to val:class Node {
int val, cnt;
Node left, right;
Node(int val) {
this.val = val;
this.cnt = 1;
}
}
The searching and insertion operations can be done as follows:
private int search(Node root, long val) {
if (root == null) {
return 0;
} else if (val == root.val) {
return root.cnt;
} else if (val < root.val) {
return root.cnt + search(root.left, val);
} else {
return search(root.right, val);
}
}
private Node insert(Node root, int val) {
if (root == null) {
root = new Node(val);
} else if (val == root.val) {
root.cnt++;
} else if (val < root.val) {
root.left = insert(root.left, val);
} else {
root.cnt++;
root.right = insert(root.right, val);
}
return root;
}
And finally the main program, in which we will search for all elements no less than twice of current element plus
1 (converted to longtype to avoid overflow) while insert the element itself into the BST.
Note: this homemade BST is not self-balanced and the time complexity can go as bad as
O(n^2) (in fact you will get TLE if you copy and paste the solution here). To guarantee O(nlogn) performance, use one of the self-balanced BST's (e.g. Red-black tree, AVLtree, etc.).public int reversePairs(int[] nums) {
int res = 0;
Node root = null;
for (int ele : nums) {
res += search(root, 2L * ele + 1);
root = insert(root, ele);
}
return res;
}
2.
BIT-based solution
For
BIT, the searching and insertion operations are:private int search(int[] bit, int i) {
int sum = 0;
while (i < bit.length) {
sum += bit[i];
i += i & -i;
}
return sum;
}
private void insert(int[] bit, int i) {
while (i > 0) {
bit[i] += 1;
i -= i & -i;
}
}
And the main program, where again we will search for all elements greater than twice of current element while insert the element itself into the BIT. For each element, the
"index" function will return its index in the BIT. Unlike the BST-based solution, this is guaranteed to run at O(nlogn).public int reversePairs(int[] nums) {
int res = 0;
int[] copy = Arrays.copyOf(nums, nums.length);
int[] bit = new int[copy.length + 1];
Arrays.sort(copy);
for (int ele : nums) {
res += search(bit, index(copy, 2L * ele + 1));
insert(bit, index(copy, ele));
}
return res;
}
private int index(int[] arr, long val) {
int l = 0, r = arr.length - 1, m = 0;
while (l <= r) {
m = l + ((r - l) >> 1);
if (arr[m] >= val) {
r = m - 1;
} else {
l = m + 1;
}
}
return l + 1;
}
II -- Partition recurrence relation
For partition recurrence relation, setting
i = 0, j = n - 1, m = (n-1)/2, we have:T(0, n - 1) = T(0, m) + T(m + 1, n - 1) + C
where the subproblem
C now reads "find the number of important reverse pairs with the first element of the pair coming from the left subarray nums[0, m] while the second element of the pair coming from the right subarray nums[m + 1, n - 1]".
Again for this subproblem, the first of the two aforementioned conditions is met automatically. As for the second condition, we have as usual this plain linear scan algorithm, applied for each element in the left (or right) subarray. This, to no surprise, leads to the
O(n^2)naive solution.
Fortunately the observation holds true here that the order of elements in the left or right subarray does not matter, which prompts sorting of elements in both subarrays. With both subarrays sorted, the number of important reverse pairs can be found in linear time by employing the so-called two-pointer technique: one pointing to elements in the left subarray while the other to those in the right subarray and both pointers will go only in one direction due to the ordering of the elements.
The last question is which algorithm is best here to sort the subarrays. Since we need to partition the array into halves anyway, it is most natural to adapt it into a
Merge-sort. Another point in favor of Merge-sort is that the searching process above can be embedded seamlessly into its merging stage.
So here is the
Merge-sort-based solution, where the function "reversePairsSub" will return the total number of important reverse pairs within subarray nums[l, r]. The two-pointer searching process is represented by the nested while loop involving variable p, while the rest is the standard merging algorithm.public int reversePairs(int[] nums) {
return reversePairsSub(nums, 0, nums.length - 1);
}
private int reversePairsSub(int[] nums, int l, int r) {
if (l >= r) return 0;
int m = l + ((r - l) >> 1);
int res = reversePairsSub(nums, l, m) + reversePairsSub(nums, m + 1, r);
int i = l, j = m + 1, k = 0, p = m + 1;
int[] merge = new int[r - l + 1];
while (i <= m) {
while (p <= r && nums[i] > 2L * nums[p]) p++;
res += p - (m + 1);
while (j <= r && nums[i] >= nums[j]) merge[k++] = nums[j++];
merge[k++] = nums[i++];
}
while (j <= r) merge[k++] = nums[j++];
System.arraycopy(merge, 0, nums, l, merge.length);
return res;
}
III -- Summary
Many problems involving arrays can be solved by breaking down the problem into subproblems applied on subarrays and then link the solution to the original problem with those of the subproblems, to which we have sequential recurrence relation and partition recurrence relation. For either case, it's crucial to identify the subproblem
C and find efficient algorithm for approaching it.
If the subproblem
C involves searching on "dynamic searching space", try to consider data structures that support relatively fast operations on both searching and updating (such as self-balanced BST, BIT, Segment tree, ...).
If the subproblem
C of partition recurrence relation involves sorting, Merge-sort would be a nice sorting algorithm to use. Also, the code could be made more elegant if the solution to the subproblem can be embedded into the merging process.
If there are overlapping among the subproblems
T(i, j), it's preferable to save the intermediate results for future lookup.
Last let me name a few leetcode problems that fall into the patterns described above and thus can be solved with similar ideas.
For
leetcode 315, applying the sequential recurrence relation (with j fixed), the subproblem C reads: find the number of elements out of visited ones that are smaller than current element, which involves searching on "dynamic searching space"; applying the partition recurrence relation, we have a subproblem C: for each element in the left half, find the number of elements in the right half that are smaller than it, which can be embedded into the merging process by noting that these elements are exactly those swapped to its left during the merging process.
For
leetcode 327, applying the sequential recurrence relation (with j fixed) on the pre-sum array, the subproblem C reads: find the number of elements out of visited ones that are within the given range, which again involves searching on "dynamic searching space"; applying the partition recurrence relation, we have a subproblem C: for each element in the left half, find the number of elements in the right half that are within the given range, which can be embedded into the merging process using the two-pointer technique.http://blog.csdn.net/kakitgogogo/article/details/55097648
给一个序列，要求求出其中“重要反转对”的个数。如果用暴力的方法对每个数nums[i]都找一遍符合
nums[i] > 2*nums[j]，要运算n*(n-1)/2次。参考discuss的答案。。用merge_sort的想法来实现。对当前的序列二分，对每个子序列，求出在每个子序列中“重要反转对”的个数（递归实现），然后对每个子序列用merge_sort排序。这样得到两个子序列各自的“重要反转对”的个数，还有排序后的子序列，然后两个子序列各自的“重要反转对”的个数的和，再加上第一个子序列中的数和第二个子序列中的数作比较符合要求的总数（因为已经排好序所以容易实现），就能得到当前序列的“重要反转对”的个数，最后将两个子序列merge_sort并返回当前结果。要注意的是比较nums[i] > 2*nums[j]时，会出现2*nums[j]溢出int的范围，所以要注意转换成long long。这道题一看就是二分查找的典型题，再用一个同样大的数组保存元素2*nums的值，然后对这个数组排序。剩下的操作都是显而易见了，全是二分查找的基本操作
LintCode - Reverse Pairs
http://www.jiuzhang.com/solutions/reverse-pairs/
public long reversePairs(int[] A) { return mergeSort(A, 0, A.length - 1); } private int mergeSort(int[] A, int start, int end) { if (start >= end) { return 0; } int mid = (start + end) / 2; int sum = 0; sum += mergeSort(A, start, mid); sum += mergeSort(A, mid+1, end); sum += merge(A, start, mid, end); return sum; } private int merge(int[] A, int start, int mid, int end) { int[] temp = new int[A.length]; int leftIndex = start; int rightIndex = mid + 1; int index = start; int sum = 0; while (leftIndex <= mid && rightIndex <= end) { if (A[leftIndex] <= A[rightIndex]) { temp[index++] = A[leftIndex++]; } else { temp[index++] = A[rightIndex++]; sum += mid - leftIndex + 1; } } while (leftIndex <= mid) { temp[index++] = A[leftIndex++]; } while (rightIndex <= end) { temp[index++] = A[rightIndex++]; } for (int i = start; i <= end; i++) { A[i] = temp[i]; } return sum; }
X. Segment tree
https://leetcode.com/problems/reverse-pairs/discuss/97310/Java-Segment-Tree-Solution
https://leetcode.com/problems/reverse-pairs/discuss/171765/O(N*log(MAXN)-)Sparse-segment-tree-solution-getting-TLE.
