面试题51：数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

解题思路

• 暴力枚举（O(n^2)，对于10^5的数组长度，显然会超时）
• 分治思想

上代码（C++很香）

  根据归并排序的分治思想，可以在归并排序的“合并”过程中，计算统计出逆序对数。

#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include "TreeNode.h"
using namespace std;

long long numN = 0;

void merge(vector<int> &a, int low, int middle, int high) {
    int i = low, j = middle + 1, k = 0;
    int tmp[high - low + 1];
    while (i<=middle && j<=high) {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else{
            // 统计i与middle之间，比a[j]大的元素个数
            numN = (numN + (middle - i + 1))% 1000000007;
            tmp[k++] = a[j++];
        }
    }

    // 处理剩下的
    while (i <= middle)
        tmp[k++] = a[i++];

    while (j <= high)
        tmp[k++] = a[j++];

    // 从tmp拷贝回a
    for (i = 0; i < high - low + 1; ++i) {
        a[low + i] = tmp[i];
    }
}

int MSort(vector<int> &a, int low, int high){
    if(low >= high)
        return 0;
    int middle = low + ((high - low) >> 1);
    MSort(a, low, middle);
    MSort(a, middle + 1, high);
    merge(a, low, middle, high);
    return numN;
}

int InversePairs(vector<int> data) {
    return MSort(data, 0, data.size() - 1);
}


int main(int argc, char* argv[]){

    vector<int> vec;
    vec.push_back(9);
    vec.push_back(8);
    vec.push_back(7);
    vec.push_back(6);
    vec.push_back(5);
    vec.push_back(4);
    vec.push_back(3);

    cout<<InversePairs(vec, 0, 6)<<endl;

    return 0;
}