题目描述
- 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对
- 输入一个数组，求出这个数组中的逆序对的总数
- 例如，在数组 {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 范围太小了吧..
- 归并排序的思路值得借鉴，貌似归并排序比快速排序还快
