逆序数
LeetCode 315. Count of Smaller Numbers After Self
很经典的一道题
已知数组nums，求新数组count，count[i]代表了在nums[i]右侧且比 nums[i]小的元素个数。 nums = [5, 2, 6, 1], count = [2, 1, 1, 0]; nums = [6, 6, 6, 1, 1, 1], count = [3, 3, 3, 0, 0, 0]; nums = [5, -7, 9, 1, 3, 5, -2, 1], count = [5, 0, 5, 1, 2, 2, 0, 0];
class Solution{
public:
std::vector<int> countSmaller(std::vector<int> &nums);
};思考与分析
最暴力的方法，即对每个元素扫描其右侧比它小的数，累加个数。假设数组元素 个数为N，算法复杂度 O(N^2)。 观察如下数组，该数组前4个元素有序，后4个元素有序，是否有更好的方法计算 count数组? 如果将这两段有序的数组归并为一个有序的数组，可否在归并排序时，将逆序数计 算出来?
算法设计
在归并该数组的前后两段有序数据时，即可将数组的全部逆序数计算出来，实际上，该数组 前半段有序数据有逆序数，后半段有序数据逆序数均为0。 在归并两段有序数据时，当需要将前一个数组元素的指针i指向的元素插入时，对应的count[i] ，即为指向后一个数组的指针j的值。 [图片上传失败...(image-af6ded-1524978344454)]
1.由于数组中的元素是随机的，一般不会分为前后两段有序的数据，如何在数据整体归并排 序时，计算出各个元素的逆序数? 2.由于归并排序时对原数组进行了排序，最终输出的count数组需要与原nums个数据对应起来， 如何解决?
解决方案
1.将元素nums[i]与元素的位置i绑定为pair，如<nums[i], i>，排序时，按照nums[i]的大小对 pair对进行排序，这样无论nums[i]如何排序，都知道nums[i]在原数组中的哪个位置。 2.利用pair对<nums[i], i>中的i对count[i]进行更新，任何一次子数组的归并，都可以认为是前 半段与后半段有序数组逆序数的计算，只需根据绑定的位置i将逆序数累加至count数组中。
#include<vector>
class Solution{
public:
std::vector<int> countSmaller(std::vector<int> &nums){
std::vector<std::pair<int,int>> vec;
std::vector<int> count;
for( int i = 0; i< nums.size();i++){
vec.push_back(std::make_pair(nums[i],i));
count.push_back(0);
}
merge_sort(vec,count);
return count;
}
private:
void merge_sort_two_vec(std::vector<std::pair<int,int>> &sub_vec1,
std::vector<std::pair<int,int>> &sub_vec2,
std::vector<std::pair<int,int>> &vec,std::vector<int> &count){}
void merge_sort(std::vector<std::pair<int,int>> &vec,std::vector<int> & count){
if(vec.size() < 2){
return;
}
int mid = vec.size() / 2;
std::vector<std::pair<int,int>> sub_vec1;
std::vector<std::pair<int,int>> sub_vec2;
for(int i = 0; i < mid; i++){
sub_vec1.push_back(vec[i]);
}
for(int i = mid; i< vec.size(); i++){
sub_vec2.push_back(vec[i]);
}
merge_sort(sub_vec1, count);
merge_sort(sub_vec2, count);
vec.clear();
merge_sort_two_vec(sub_vec1,sub_vec2,vec,count);
}
};void merge_sort_two_vec(std::vector<std::pair<int,int>> &sub_vec1,
std::vector<std::pair<int,int>> &sub_vec2,
std::vector<std::pair<int,int>> &vec,std::vector<int> &count){
int i = 0;
int j = 0;
while(i < sub_vec1.size() && j < sub_vec2.size()){
if(sub_vec1[i] .first< sub_vec2[j].first){
count[sub_vec1[i].second] + = j;
vec.push_back(sub_vec1[1]);
i++;
}
else{
sec.push_back(sub_vec2[j]);
j++;
}
}
for (; i<sub_vec1.size();i++){
count[sub_vec1[i].second] += j;
vec.push_back(sub_vec1[i]);
}
for(;j< sub_vec2.size();j++){
vec.push_back(sub_vec2[j]);
}
}