归并排序求逆序对

数组中的逆序对

http://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5

class Solution {
public:
    int t[200005];
    long long merge_sort(vector<int> &data, int l, int r) {
        long long num = 0;
        if(l < r) {
            int mid = (l + r) / 2;
            num += merge_sort(data, l, mid) % 1000000007;
            num += merge_sort(data, mid + 1, r) % 1000000007;
            int i = l, j = mid + 1, k = 0;
            while(i <= mid && j <= r) {
                if(data[i] > data[j]) t[k ++] = data[j ++], num += mid - i + 1;
                else t[k ++] = data[i ++];
            }
            while(i <= mid) t[k ++] = data[i ++];
            while(j <= r) t[k ++] = data[j ++];
            for(int i = l; i <= r; i ++) data[i] = t[i - l];
        }
        return num % 1000000007;
    }


    int InversePairs(vector<int> data) {
        return merge_sort(data, 0, data.size() - 1);
    }
};
全部评论

相关推荐

Lorn的意义:1.你这根本就不会写简历呀,了解太少了 2.你这些项目经历感觉真的没啥亮点啊,描述的不行,重写书写一下让人看到核心,就继续海投 注意七八月份ofer还是比较多的,越往后机会越少,抓住时机,抓紧检查疏漏,加油查看图片
点赞 评论 收藏
分享
点赞 评论 收藏
分享
07-18 18:44
已编辑
中山职业技术学院 Java
投递文远知行等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务