题解 | #数组中的逆序对#
数组中的逆序对
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
class Solution {
private:
int m_cnt = 0;
public:
vector<int> div(vector<int> &data, int start, int end){
vector<int> temp;
//temp.reserve(end-start);
if(start==end) {temp.push_back(data[start]);return temp;}
temp.reserve(end-start);
int mid = (end+start)/2;
vector<int> left = div(data, start, mid);
vector<int> right = div(data, mid+1, end);
int size1 = left.size();
int size2 = right.size();
for(int ii=0; ii<size1;ii++){
for(int jj=0; jj<size2; jj++){
if(left[ii]>right[jj]){
int cnt = size2-jj;
m_cnt = (m_cnt+cnt)%1000000007;
break;
}
}
}
int i=0, j=0;
while(i<size1&&j<size2){
if(left[i]>right[j]){
temp.push_back(left[i]);
i++;
}else{
temp.push_back(right[j]);
j++;
}
}
if(i>=size1){
while(j<size2) {
temp.push_back(right[j]);
j++;
}
}
if(j>=size2){
while(i<size1) {
temp.push_back(left[i]);
i++;
}
}
return temp;
}
int InversePairs(vector<int> data) {
int size = data.size();
if(size==0) return 0;
vector<int> ans;
ans.reserve(size);
div(data,0,size-1);
return m_cnt;
}
};
查看10道真题和解析
投递远光软件等公司6个岗位 >
中国移动开奖1人在聊