逆序对问题

简介: 逆序对问题

Reverse pair

问题

一个数组,其中一个数的左边有数大于其本身,则称它们形成逆序对,求逆序对的数量

思路

利用归并排序,综合小和问题解决

实现

int ReversePair(int arr[],int lenth)
{
   if(lenth < 2) return 0;
    return process(arr,0,lenth - 1);
}
int process(int arr[],int L,int R)
{
    if(L >= R) return 0;
    int mid = (L + ((R - L) >> 1));
    return process(arr,L,mid) + process(arr,mid + 1,R) + merge(arr,L,mid,R);
}
int merge(int arr[],int L,int mid,int R)
{
    int help[R - L + 1];
    int p1 = L;
    int p2 = mid + 1;
    int i = 0;
    int res = 0;
    while(p1 <= mid && p2 <= R)
    {
        res += arr[p1] > arr[p2] ? (mid - p1 + 1) : 0;
        help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
    }
    while(p1 <= mid)
    {
        help[i++] = arr[p1++];
    }
    while(p2 <= R)
    {
        help[i++] = arr[p2++];
    }
    for(i = 0;i < R - L + 1;i++)
    {
        arr[L + i] = help[i];
    }
    return res;
}

总结

归并排序,划分两个区域,根据左区域下标算出,左边有多少数大于右边。

luck++
+关注
目录
打赏
0
0
0
0
0
分享
相关文章
alist对接钉钉sso登录
本文介绍了如何将Alist与钉钉SSO登录对接。Alist是一个基于Go语言开发的文件管理程序,支持多平台和多种存储方式。通过设置自定义头部、配置钉钉开放平台应用及回调参数,并获取Client ID和Client Secret,可实现钉钉SSO登录功能。最后根据需求配置用户权限,默认权限值可通过相加不同权限数字获得。成品展示了一个美观且实用的文件管理系统。
435 8
alist对接钉钉sso登录
Linux C++ 环境下数据高效备份策略:全面指南与最佳实践
Linux C++ 环境下数据高效备份策略:全面指南与最佳实践
139 1
阿里云国际站代理商:阿里云使用 odps-jdbc 接入 ODPS是如何操作的?
@luotuoemo飞机@TG 阿里云国际站代理商:阿里云使用 odps-jdbc 接入 ODPS是如何操作的?在代码中,你需要使用`Class.forName`加载odps-jdbc驱动类,然后通过`DriverManager.getConnection`方法建立与ODPS的数据库连接:
canvas自定义绘制顺序解决遮挡问题
canvas自定义绘制顺序解决遮挡问题
416 0
09 OpenCV图形检测
cv2.findContours() 函数是OpenCV中用于寻找轮廓的函数之一。它可以用于在二值图像中查找并检测出所有的物体轮廓,以及计算出这些轮廓的各种属性,例如面积、周长、质心等。
阿里云服务器默认专有网络和交换机是什么?
2023阿里云服务器默认专有网络和交换机是什么?阿里云服务器网络及可用区,网络指的是专有网络VPC,可用区是指同一个地域下网络和电力相互独立的区域,专有网络是用户在云端的私有网络,专有网络之间逻辑上彻底隔离,用户可以在专有网络上设置IP地址段、交换机和路由表等。阿里云百科来详细说下什么是专有网络以及可用区选择方法:
461 0
阿里云服务器默认专有网络和交换机是什么?
Hive-加载数据与数据null值处理
本文讲述了实战中Hive加载业务数据基础全过程,以及加载数据的null值处理。这是一篇讲述了比较简单的案例,后面会分享其他实战经验。
Hive-加载数据与数据null值处理
登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问