Reverse Pairs 532
Question
For an array A, if i < j, and A [i] > A [j], called (A [i], A [j]) is a reverse pair. return total of reverse pairs in A.
Example
Given A = [2, 4, 1, 3, 5] , (2, 1), (4, 1), (4, 3) are reverse pairs. return 3
Solution
最容易想到的方法是依次查看每个元素和其后面所有元素是否是reverse pairs。但是该方法为O(n^2),不够快。
O(nlogn)方法:利用mergetSort的性质,即将数组分为左右两个子数组,左边数组元素index都小于右边数组元素index,同时在merge的时候会挨个比较左右两个数组元素大小,此时只要左边数组某一个元素i大于右边数组某一个元素j,则从i开始到左边数组最后一个元素和j都是reverse pairs的关系。因此,每一次merge都能寻找reverse pairs。对于每一次切割,其reverse pairs为左边数组merge找到的reverse pairs的个数 + 右边数组merge找到的reverse pairs的个数 + 左右数组merge找到的reverse pairs的个数。
代码如下:
public class Solution {
/**
* @param A an array
* @return total of reverse pairs
*/
public long reversePairs(int[] A) {
// Write your code here
if(A == null || A.length == 0){
return 0;
}
return mergeSort(A, 0, A.length - 1);
}
private long mergeSort(int[] A, int start, int end){
if(start >= end){
return 0;
}
long sum = 0;
int mid = (start + end) / 2;
sum += mergeSort(A, start, mid);
sum += mergeSort(A, mid + 1, end);
sum += merge(A, start, mid, end);
return sum;
}
private long merge(int[] A, int start, int mid, int end){
int[] temp = new int[A.length];
int left = start;
int right = mid + 1;
int index = start;
long sum = 0;
while(left <= mid && right <= end){
if(A[left] <= A[right]){
temp[index++] = A[left++];
}else{
temp[index++] = A[right++];
sum += mid - left + 1;
}
}
while(left <= mid){
temp[index++] = A[left++];
}
while(right <= end){
temp[index++] = A[right++];
}
for(int i = start; i <= end; i++){
A[i] = temp[i];
}
return sum;
}
}