逆序数

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]);
        }

}