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

数组中的逆序对

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

  1. 首先是归并。然后归并的时候进行比较
class Solution {
public:
    int count = 0;
    int InversePairs(vector<int> data) {
        if(data.size()<2) return 0;
        // 长度小于2则无逆序对

        mergeSort(data,0,data.size()-1);

        return count;

    }

    void mergeSort(vector<int>& data, int left, int right){

        int mid = (left+right)/2;

        if(left<right){
            //
            mergeSort(data,left,mid);
            mergeSort(data,mid+1,right);

            merge(data,left,mid,right);

        }
    }


    void merge(vector<int>& data, int left,int mid, int right){

        vector<int> arr(right - left+1,0);
        int i = left, j = mid+1, k = 0, origin = left;


        while(i<=mid&&j<=right){
            if(data[i]<=data[j]){
                arr[k++] = data[i++];
            }else{
                arr[k] = data[j];

                count += mid+1-i;
                count %= 1000000007;

                k++;
                j++;

            }
        }

        // 左子数组还有元素时,全部放入临时数组
        for(;i<=mid;){
            arr[k++] = data[i++];
        }
        // 右子数组还有元素时,全部放入临时数组
         for(;j<=right;){
            arr[k++] = data[j++];
        }
        // 将临时数组中的元素放入到原数组的指定位置
        for(int num:arr){
            data[origin++] = num;
        }

    }
};
大厂笔试题题解 文章被收录于专栏

主要是公司笔试题得一些总结

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 11:33
点赞 评论 收藏
分享
05-19 19:57
蚌埠学院 Python
2237:Gpa70不算高,建议只写排名,个人技能不在多而在精,缩到8条以内。项目留一个含金量高的,减少间距弄到一页,硕士简历也就一页,本科不要写很多
实习,投递多份简历没人回...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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