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

糖逗

题目描述：

1. 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
   
2. 
   
3.  
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: [7,5,6,4]
   
8. 输出: 5
   
9.  
   
10. 
    
11. 限制：
    
12. 
    
13. 0 <= 数组长度 <= 50000
    
14. 
    
15. 来源：力扣（LeetCode）
    
16. 链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
    
17. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include<vector>
   
2. #include<iostream>
   
3. 
   
4. using namespace std;
   
5. 
   
6. int count = 0;
   
7. 
   
8. void merge(vector<int>& input, int left, int middle, int middle_, int right){
   
9.         int* temp = new int[right - left + 1];
   
10.         int temp1 = left, temp2 = middle_;
    
11.         int r = 0;
    
12.         while(temp1 <= middle && temp2 <= right){
    
13.                 if(input[temp1] <= input[temp2]){
    
14.                         temp[r++] = input[temp1++];
    
15.                 }
    
16.                 else{
    
17.                         temp[r++] = input[temp2++];
    
18.                         count += middle - temp1+1;
    
19.                 }
    
20.         }
    
21.         while(temp1 <= middle){
    
22.                 temp[r++] = input[temp1++];
    
23.         }
    
24.         while(temp2 <= right){
    
25.                 temp[r++] = input[temp2++];
    
26.         }
    
27.         for(int i = 0; i < right - left + 1; i++){
    
28.                 input[left + i] = temp[i];
    
29.         }
    
30.         delete [] temp;
    
31. }
    
32. 
    
33. 
    
34. void solution(vector<int>& input, int left, int right){
    
35.         if(left >= right) return;
    
36.         int middle = left + (right - left)/2;
    
37.         solution(input, left, middle);
    
38.         solution(input, middle+1, right);
    
39.         merge(input, left, middle, middle+1, right);
    
40. }
    
41. 
    
42. 
    
43. int result(vector<int> & input){
    
44.         solution(input, 0, input.size()-1);
    
45.         return count;
    
46. }
    
47. 
    
48. int main(void){
    
49.         vector<int> input;
    
50.         int number;
    
51.         while(cin >> number){
    
52.                 input.push_back(number);
    
53.         }
    
54.         int res = result(input);
    
55.         cout << res << endl;
    
56.         return 0;
    
57. }

复制代码

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