统计序列中的逆序对
因为好像做过这个题目，所以稍微提一下。最简单的方式就是归并排序 题解 方法分别是归并排序和树状数组。
归并排序
代码来源：https://blog.csdn.net/afei__/article/details/82951905 我觉得这个写的好一些。并且官方题解里面是写反的，我一开始还看了半天。
public class Main {
public static void main(String[] args) {
int[] arr = new int[] { 2, 3, 8, 6, 1 };
int inversionCount = mergeSort(arr, 0, arr.length);
printArray(arr);
System.out.println("inversionCount: " + inversionCount);
}
public static int mergeSort(int[] arr, int start, int end) {
int inversionCount = 0;
int length = end - start;
if (length > 1) { // 长度大于1才需要排序
int mid = (start + end) / 2;
inversionCount += mergeSort(arr, start, mid); // sort left
inversionCount += mergeSort(arr, mid, end); // sort right
inversionCount += merge(arr, start, mid, end);
}
return inversionCount;
}
public static int merge(int[] arr, int start, int mid, int end) {
// check input
if (arr == null || start < 0 || end > arr.length) {
return 0;
}
int[] temp = new int[end - start];
int inversionCount = 0;
int i = start; // 左半部分索引
int j = mid; // 右半部分索引
int k = 0; // temp数组索引
while (i < mid && j < end) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
// 一旦 arr[i] > arr[j]，就会有 (mid - i) 个逆序对产生
inversionCount += mid - i;
}
}
if (i != mid) {
System.arraycopy(arr, i, temp, k, mid - i);
}
if (j != end){
System.arraycopy(arr, j, temp, k, end - j);
}
System.arraycopy(temp, 0, arr, start, temp.length);
return inversionCount;
}
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}树状数组
思路是这样的，对于一个给定的数组a,比如[5,5,2,3,6]，从后往前遍历，并统计其前缀和。 每加入一个数字，其添加的逆序对的个数就等于i-1位的前缀和。 以该例子作为示范，显然6,3,2都没有逆序，在输入第一个5的时候，其前缀和表示所有小于等于4的数字的数量，等于2； 以此类推，将逆序对求解转变为了求解动态前序和的问题。
由于前序和动态变化，最好的方式就是树状数组。使用官方代码
class BIT {
private:
vector<int> tree;
int n;
public:
BIT(int _n): n(_n), tree(_n + 1) {}
static int lowbit(int x) {
return x & (-x);
}
int query(int x) {
int ret = 0;
while (x) {
ret += tree[x];
x -= lowbit(x);
}
return ret;
}
void update(int x) {
while (x <= n) {
++tree[x];
x += lowbit(x);
}
}
};
class Solution {
public:
int reversePairs(vector<int>& nums) {
int n = nums.size();
vector<int> tmp = nums;//tmp保存前缀和
// 离散化，将具体数字转为对应的排名。说实话我来做的话可能只能开个map来存了，应该是想不到lower_bound的用法
sort(tmp.begin(), tmp.end());
for (int& num: nums) {
num = lower_bound(tmp.begin(), tmp.end(), num) - tmp.begin() + 1;
}
// 树状数组统计逆序对
BIT bit(n);
int ans = 0;
for (int i = n - 1; i >= 0; --i) {
ans += bit.query(nums[i] - 1);//求解n-1的前缀和
bit.update(nums[i]);//把i增加进去
}
return ans;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-03-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
