逆序对问题

2018-03-26 22:02:36

逆序对定义：

对于一个包含N个非负整数的数组A[1..n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ,A[ j] )为数组A中的一个逆序对。

例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。

逆序对问题就是求解一个数组中的逆序对的个数，逆序对问题是个非常经典的问题。当然可以写出一个在O(n ^ 2)时间复杂度解决的算法，这里就不对这种naive的解法做介绍了，主要会讲解两种O(nlogn)的解法。

 

一、树状数组

通过树状数组求解逆序对是个很经典的解法，树状数组的特点是单点更新，区间求和，使用树状数组求解逆序对从本质来说就是一个求和问题，我们可以为每个数字构建一个桶，出现了就在该桶里的数目上加1，可以倒序遍历数组，当遍历到某个数的时候，求getsum(nums[i])，即求解i位后的比a[i]小的数的个数，最后求总和就是结果。

桶排序的问题，这里也会出现，也就是数组中的区间范围如果非常庞大，那么建立max + 1大小的桶就非常的不合算，这时候就需要使用离散化的技术进行预处理。

使用树状数组的时间复杂度为O(nlogn)。

• 离散化

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：

原数据：1,999,100000,15；处理后：1,3,4,2；

注意到，离散化后的数组中的逆序对和原数组是相等的。

在C++中可以借助STL进行离散化：

思路是：先排序，再删除重复元素，最后就是索引元素离散化后对应的值。

 

假定待离散化的序列为a[n]，sub_a[n]是序列a[n]的一个副本，则对应以上三步为：

sort(sub_a,sub_a+n);

int size=unique(sub_a,sub_a+n)-sub_a;//size为离散化后元素个数

for(i=0;i<n;i++)

a[i]=lower_bound(sub_a,sub_a+size,a[i])-sub_a + 1;

• 树状数组求解问题

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int[] sorted = Arrays.copyOf(nums, nums.length);
        Arrays.sort(sorted);
        Map<Integer, Integer> ranks = new HashMap<>();
        int rank = 0;
        for (int i = 0; i < sorted.length; ++i)
            if (i == 0 || sorted[i] != sorted[i - 1])
                ranks.put(sorted[i], ++rank);
        int[] bit = new int[ranks.size() + 1];
        for (int i = nums.length - 1; i >= 0; --i) {
            int sum = query(bit, ranks.get(nums[i]) - 1);
            res.add(sum);
            update(bit, ranks.get(nums[i]), 1);
        }
        Collections.reverse(res);
        return res;
    }

    private int query(int[] bit, int i) {
        int res = 0;
        for (int k = i; k > 0; k -= (k & -k)) {
            res += bit[k];
        }
        return res;
    }

    private void update(int[] bit, int i, int delta) {
        for (int k = i; k < bit.length; k += (k & -k)) {
            bit[k] += delta;
        }
    }

 

二、归并排序

归并排序在merge的过程中天然会进行前后数的比较，因此使用归并排序来求解逆序对问题就水到渠成了。

时间复杂度： O(nlogn)。

public class MergeSort {
    int merge(int[] nums, int[] tmp, int L, int R, int REnd) {
        int res = 0;
        int index = L;
        int len = REnd - L + 1;
        int LEnd = R - 1;
        while (L <= LEnd && R <= REnd) {
            if (nums[R] < nums[L]) {
                res += LEnd - L + 1;
                tmp[index++] = nums[R++];
            }
            else tmp[index++] = nums[L++];
        }
        while (L <= LEnd) tmp[index++] = nums[L++];
        while (R <= REnd) tmp[index++] = nums[R++];
        for (int i = 0; i < len; i++, REnd--) {
            nums[REnd] = tmp[REnd];
        }
        return res;
    }

    int mergeSort(int[] nums, int[] tmp, int L, int REnd) {
        if (L < REnd) {
            int mid = (REnd - L) / 2 + L;
            return mergeSort(nums, tmp, L, mid) + mergeSort(nums, tmp, mid + 1, REnd) +
                    merge(nums, tmp, L, mid + 1, REnd);
        }
        return 0;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 3, 8, 6, 1};
        MergeSort ms = new MergeSort();
        System.out.println(ms.mergeSort(nums, new int[nums.length], 0, nums.length - 1));
    }
}