C++刷剑指offer（面试题51. 数组中的逆序对）【归并排序】

糖逗

题目描述：

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

 

示例 1:

输入: [7,5,6,4]
输出: 5
 

限制：

0 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<vector>
#include<iostream>

using namespace std;

int count = 0;

void merge(vector<int>& input, int left, int middle, int middle_, int right){
        int* temp = new int[right - left + 1];
        int temp1 = left, temp2 = middle_;
        int r = 0;
        while(temp1 <= middle && temp2 <= right){
                if(input[temp1] <= input[temp2]){
                        temp[r++] = input[temp1++];
                }
                else{
                        temp[r++] = input[temp2++];
                        count += middle - temp1+1;
                }
        }
        while(temp1 <= middle){
                temp[r++] = input[temp1++];
        }
        while(temp2 <= right){
                temp[r++] = input[temp2++];
        }
        for(int i = 0; i < right - left + 1; i++){
                input[left + i] = temp[i]; 
        }
        delete [] temp;
}


void solution(vector<int>& input, int left, int right){
        if(left >= right) return;
        int middle = left + (right - left)/2;
        solution(input, left, middle);
        solution(input, middle+1, right);
        merge(input, left, middle, middle+1, right);
}


int result(vector<int> & input){
        solution(input, 0, input.size()-1);
        return count;
}

int main(void){
        vector<int> input;
        int number;
        while(cin >> number){
                input.push_back(number);
        }
        int res = result(input);
        cout << res << endl;
        return 0;
} 

注意事项：
1.在归并排序的基础加一行代码。