广州北大青鸟计算机职业培训学校
互联网技术培训、软件技术培训、大数据培训、云计算培训、数据分析培训信息网
当前位置:网站首页 > 计算机教程 > 正文

Java培训

作者:adminjiang发布时间:2021-07-15分类:计算机教程浏览:585


导读:  如果一个数组在排序之后,每相邻两个数差的绝对值都为1,则该数组为可整合数组。例如:[5,3,4,6,2]排序之后为[2,3,4,5,6],符合每相邻两个数差的绝对值都为1,所以...


  如果一个数组在排序之后,每相邻两个数差的绝对值都为1,则该数组为可整合数组。例如:[5,3,4,6,2]排序之后为[2,3,4,5,6],符合每相邻两个数差的绝对值都为1,所以这个数组为可整合数组。




  给定一个整型数组arr,要求返回其中最大可整合数组的长度。例如,[5,5,3,2,6,4,3]的最大整合子数组为[5,3,2,6,4],所以返回5.


  时间复杂度高但容易理解的做法。对arr中的每一个子数组arr[i……j](0<=i<=j<=N-1),都验证一下是否符合可整合数组的定义,也就是把arr[i……j]排序一下,看是否依次递增且每次递增1.然后在所有符合整合数组定义的子数组中,记录最大的那个长度,返回即可。需要注意的是,在考查每一个arr[i……j]是否符合可整合数组定义的时候,都得把arr[i……j]单独复制成一个新的数组,然后把这个新的数组排序、验证,而不能直接改变arr中元素的顺序。大体过程如下:依次考查每一个子数组arr[i……j](0<=i<=j<=N-1),一共有O(N^2)个。2.对每一个子数组arr[i……j],复制成一个新的数组,记为newArr,把newArr排序,然后验证是否符合可整合数组的定义,这一步代价为O(NlogN)。3.步骤2中符合条件的、最大的那个子数组的长度就是结果。


  具体过程看如下代码中的getLIL1方法,时间复杂度为O(N^2)*O(NlogN)-O(N^3logN).




  第一种方法严格按照定义来验证每一个子数组是否是可整合数组,但是验证可整合数组真的需要如此麻烦吗?有没有更好的方法来加速验证过程?这也是下面要提供方法的核心。判断一个数组是否是可整合数组还可以用以下方法来判断,一个数组中如果没有重复元素,并且如果最大值减去最小值,再加1的结果等于元素个数(max-min+1==元素个数),那么这个数组就是可整合数组。比如[3,2,5,6,4],max-min+1=6-2+1=5==元素个数,所以这个数组是可整合数组。这样,验证每一个子数组是否是可整合数组的时间复杂度可以从第一种方法的O(NlogN)加速至O(1),整个过程的时间复杂度就可加速到O(N^2),具体请参看如下代码中的getLIL2方法。




  算法与数据结构--最长的可整合子数组的长度的普通解法和进阶解法(java实现)


   

      广州北大青鸟依托北京大学雄厚资源,是北大青鸟华南地区就业示范校区,学校提供学历+技能+就业服务,主要开设热门课程java培训,UI设计培训,PHP培训,Web前端培训,软件开发编程培训等全程项目实战,免费就业推荐等,详情请点击右边的咨讯框咨询在线的老师,同时还可以获取免费的试听课程,欢迎咨询哦!!!

 



计算机教程排行
标签列表
网站分类
文章归档
最近发表