归并排序:数组中的逆序对、O(n) 方法

编辑于 2017-01-23

* 移动设备下, 可左滑手指以查看较宽代码

题目

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。例如 1,2,3,4,5,6,7,0,逆序对数为 7。.

思路

归并排序,逆序执行,归并比较过程中每当出现 a[i] > a[j],必然会增加right-mid+1个逆序对。

int InversePairs(vector<int> data) {
    int len = data.size();
    if (len == 0)
        return -1;
    vector<int> tmp(data);
    long count = 0;
    count = merge_sort(data, tmp, 0, len - 1);
    return count % 1000000007;
}

long merge_sort(vector<int> &vec,  vector<int> &tmp, int left, int right) {
    if (left >= right)
        return 0;

    int mid = (left + right) / 2;
    long count = 0;
    count += merge_sort(vec, tmp, left, mid);
    count += merge_sort(vec, tmp, mid+1, right);
    count += merge(vec, tmp, left, mid, right);

    return count;
}

long merge(vector<int> &vec, vector<int> &tmp, int left, int mid, int right) {
    int i = left, j = mid+1, k = 0;
    long count = 0;
    while (i <= mid && j <= right) {
        //逆序
        if (vec[i] > vec[j]) {
            //遇到前面大于后面,说明有逆序,因为是排序的,所以逆序长度为后面的那个序列长度
            count += right - j + 1;
            tmp[k++] = vec[i++];
        } else {
            tmp[k++] = vec[j++];
        }
    }
    while (i <= mid)
        tmp[k++] = vec[i++];

    while (j <= right)
        tmp[k++] = vec[j++];

    copy(tmp.begin(), tmp.begin()+k, vec.begin()+left);

    return count;
}

O(n) 方法

此方法要求数字的范围不能太大

思路: 借助一个数组 hash ,统计 array 从后往前的情况下,到第 i 位时候,i 后面每个数字出现的次数,然后统计 hash 数组中 hash[x] 的和(x < array[i])

void InversePairs()
{
    int ans = 0;
    for(; i>= 0; i--) {
        hash[array[i]] ++;
        ans += countInversePairs(hash, array[i]);
    }
    return ans;
}

int countInversePairs(int[] hash, int target)
{
    int count = 0;
    for(int i = 0; i < target; i++) {
        count += hash[i];
    }
    return count;
}