题解 | 数组中的逆序对

数组中的逆序对

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

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    
    int coreCode(vector<int>& nums, vector<int>& temp, int left, int right){
        if(left>=right) return 0;//指向同一个位置也是没有逆序数了
        int mid = (left+right)/2;
        int pairs = (coreCode(nums, temp, left, mid)+coreCode(nums, temp, mid+1, right))%1000000007;
        int cur = left;
        int lpos = left, rpos = mid+1;
        while(cur<=right){
            if(lpos<=mid&&rpos<=right){
                if(nums[lpos]<nums[rpos]){//没有相同数字
                    temp[cur] = nums[lpos];
                    ++lpos;
                }
                else{
                    temp[cur] = nums[rpos];
                    ++rpos;
                    pairs = (pairs+mid-lpos+1)%1000000007;
                }
            }
            else if(lpos>mid){
                temp[cur] = nums[rpos];
                ++rpos;
            }
            else if(rpos>right){
                temp[cur] = nums[lpos];
                ++lpos;
            }
            ++cur;
        }
        for(int i = left; i <= right; ++i){
            nums[i] = temp[i];
        }
        return pairs;
    }
    int InversePairs(vector<int>& nums) {
        // write code here
        vector<int> temp(nums);
        return coreCode(nums, temp, 0, nums.size()-1);
    }
};

归并排序,重点在于归并知道每次合并时左右已经有序的情况下右边哪个部分跑到前面去了。

以及注意边界位置,末尾是刚好还是后一位,统一你自己的逻辑就好,我习惯刚好。

但是一般标准库函数会是后一位。

全部评论

相关推荐

06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
06-13 10:15
门头沟学院 Java
想去夏威夷的大西瓜在...:我也是27届,但是我现在研一下了啥项目都没有呀咋办,哎,简历不知道咋写
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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