题目描述

• 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对
• 输入一个数组，求出这个数组中的逆序对的总数
• 例如，在数组 {7，5，6，4} 中，一共存在 5 个逆序对，分别是 (7，6)，(7，5)，(7，4)，(6，4)，(5，4)

题目解读

• 剑指Offer 250
• 思路一，从前往后依次遍历
• 思路二，归并排序的思路，看书

代码

• 思路一，从前往后依次遍历 <牛客上没通过，估计是超时吧>

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    
    int InversePairs(vector<int> data) {
        int len = data.size();
        int result = 0;

        for(int i=0; i < len-1; i++){
            for(int j=i+1; j < len; j++){
                if(data[i] > data[j]){
                    result ++;
                }
            }
        }
        return result;
    }
};

int main(){
    Solution ss;
    vector<int> data;
    int a[10] = {7, 5, 6, 4};
    for (int i = 0; i < 4; ++i){
        data.push_back(a[i]);
    }

    cout<<ss.InversePairs(data);
}

• 思路二，归并排序的思路，看书

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:

    long long InversePairsCore(vector<int>& data, vector<int>& temp, int start, int end){
        if(start == end){
            return 0;
        }

        int mid = (start + end) >> 1;
        // 此处必须用 long long ，如果用 int 只能过 50%
        long long left = InversePairsCore(temp, data, start, mid);
        long long right = InversePairsCore(temp, data, mid+1, end);
        long long count = 0;

        int indextemp = end;
        int i = mid; // i初始化前半段最后一个数字下标
        int j = end; // j初始化为后半段最后一个数字下标

        while( i >= start && j >= mid+1){
            if(data[i] > data[j]){
                temp[indextemp--] = data[i--];
                count += j - mid;
            }
            else{
                temp[indextemp--] = data[j--];
            }
        }

        for( ; i >= start; i--){
            temp[indextemp--] = data[i];
        }

        for( ; j >= mid+1; j--){
            temp[indextemp--] = data[j];
        }

        return left+right+count;
    }

    int InversePairs(vector<int> data) {
        int length = data.size();
        if(length <= 0){
            return 0;
        }

        vector<int> temp;
        for(int i=0; i < length; i++){
            temp.push_back(data[i]);
        }

        long long result = InversePairsCore(data, temp, 0, length-1);
        return result%1000000007;
    }
};

int main(){
    Solution ss;
    vector<int> data;
    int a[10] = {7, 5, 6, 4};
    for (int i = 0; i < 4; ++i){
        data.push_back(a[i]);
    }

    cout<<ss.InversePairs(data);
}

总结展望

• 思路二，用 int 只能过 50%，后来参考牛客这道题讨论区，发现用 long long 直接过，至于原因，我个人估计是 int 范围太小了吧..
• 归并排序的思路值得借鉴，貌似归并排序比快速排序还快