统计序列中的逆序对

2021-03-17 2024-01-21 约 900 字预计阅读 2 分钟 - 次阅读

因为好像做过这个题目，所以稍微提一下。最简单的方式就是归并排序题解方法分别是归并排序和树状数组。

归并排序

代码来源：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;
    }
};