C++刷剑指offer（面试题51. 数组中的逆序对）【归并排序】
本帖最后由 糖逗 于 2020-5-8 17:43 编辑题目描述：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入:
输出: 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;
int temp1 = left, temp2 = middle_;
int r = 0;
while(temp1 <= middle && temp2 <= right){
if(input <= input){
temp = input;
}
else{
temp = input;
count += middle - temp1+1;
}
}
while(temp1 <= middle){
temp = input;
}
while(temp2 <= right){
temp = input;
}
for(int i = 0; i < right - left + 1; i++){
input = temp;
}
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.在归并排序的基础加一行代码。
页:
[1]