题解 | #数组中的逆序对#

为什么这道题大家都在用归并排序，我觉得归并排序计算逆序对的思想不是很直观。

我的方法是遍历整个数组，然后将遍历过的值插入到另一个vector中，通过二分查找找到合适的位置插入，从而保证vector是降序的，插入的同时也知道了有几个数比它大。

class Solution {
public:
    const int m = 1000000007;
    int InversePairs(vector<int> data) {        
        vector<int> v;
        int ret = 0;
        for(int i=0; i<data.size(); ++i){
            int len = v.size();
            int l = 0, r = len;
            while(l<r){
                int mid = l + (r-l)/2;
                if(data[i]>v[mid]){
                    r = mid;
                }
                else{
                    l = mid+1;
                }
            }
            ret = (ret+l)%m;
            v.insert(v.begin()+l, data[i]);
        }
        return ret;
    }
};

时间复杂度是O(nlogn)，空间复杂度O(n)

更新：由于vector的插入是O(n)复杂度，所以时间复杂度还是O(n²)。。想过用链表+哈希的方式，好像也不行，看来还是得用归并排序。