交易逆序对的总数
在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
示例 1:
输入：record = [9, 7, 5, 4, 6]
输出：8
解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
思路
方法一：嵌套 for (超时)
class Solution {
public int reversePairs(int[] record) {
int total = 0;
for(int i = 0; i < record.length; i++) {
for(int j = i + 1; j < record.length; j++){
if(record[i] > record[j]){
total++;
}
}
}
return total;
}
}
方法二：归并排序
这里在归并的过程中统计逆序对的正确性在于：对于A(在左半部分)、B(在右半部分)两个升序数组合并的过程中，当A中的某一个元素a和B中的某一个元素b比较时，如果确定a比b大，那么A中在a之后的元素的都比b大，也就是说，A中在a之后的元素以及a和b均构成了逆序对。
class Solution {
public int reversePairs(int[] record) {
if (record == null || record.length < 2) {
return 0;
}
int n = record.length;
int[] temp = new int[n];
return mergeSort(record, temp, 0, n - 1);
}
// 归并排序入口
private int mergeSort(int[] record, int[] temp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
int count = mergeSort(record, temp, left, mid) + mergeSort(record, temp, mid + 1, right);
count += merge(record, temp, left, mid, right);
return count;
} else {
return 0;
}
}
// 双指针合并两个有序数组，并计算逆序对数量
private int merge(int[] record, int[] temp, int left, int mid, int right) {
int count = 0;
int P1 = left;
int P2 = mid + 1;
int k = 0;
while (P1 <= mid && P2 <= right) {
if (record[P1] <= record[P2]) {
temp[k++] = record[P1++];
} else {
temp[k++] = record[P2++];
count += (mid - P1 + 1); // 计算逆序对数量
}
}
while (P1 <= mid) {
temp[k++] = record[P1++];
}
while (P2 <= right) {
temp[k++] = record[P2++];
}
for (int i = left; i <= right; i++) {
record[i] = temp[i - left];
}
return count;
}
}