算法复习：归并排序

2021-02-07 02:16

阅读：500

标签：hid 归并 for 有序 open cli vector pairs public

leetcode 面试题51. 数组中的逆序对

本质上就是归并排序，并在合并区间过程中统计交换的逆序对的数目

归并排序需要开o(n)的辅助空间

class Solution {
public:
    int deal(vectorint>&nums,vectorint>&tmp,int ll,int rr)
    {
        if(ll>=rr)//返回条件
            return 0;

        int mid=ll+(rr-ll)/2;
        int count=deal(nums,tmp,ll,mid)+deal(nums,tmp,mid+1,rr);
        if(nums[mid]1])//已经有序不需要再比了
            return count;

        int x=ll,y=mid+1,i;
        for(i=0;x//合并两个数组到新的数组
        {
            if(nums[x]nums[y])
            {
                tmp[i]=nums[x];
                x++;
            }
            else
            {
                tmp[i]=nums[y];
                y++;
                count+=(mid-x+1);
            }
        }
        for(;x)
        {
            tmp[i]=nums[x];
            i++;
        }
        for(;y)
        {
            tmp[i]=nums[y];
            i++;
        }
        int yy=ll;
        for(int k=0;k)
        {
            nums[yy]=tmp[k];
            yy++;
        }
        return count;
    }
    int reversePairs(vectorint>& nums) {
        int size=nums.size();
        if(size2)
            return 0;
        vectorint>tmp(size,0);
        return deal(nums,tmp,0,size-1);
    }
};

View Code

算法复习：归并排序

标签：hid 归并 for 有序 open cli vector pairs public

原文地址：https://www.cnblogs.com/dzzy/p/12778717.html

上一篇：什么是Spring?

下一篇：Python 第一个脚本

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：算法复习：归并排序
文章链接：http://soscw.com/index.php/essay/51978.html

亲，登录后才可以留言！

算法复习：归并排序

评论

热门文章

推荐文章

最新文章

置顶文章