Java培训教程：Java数组长度的普通解法和进阶解法

　　如果一个数组在排序之后，每相邻两个数差的绝对值都为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培训机构小编介绍的“Java培训教程：Java数组长度的普通解法和进阶解法”的内容，希望对大家有帮助，如有疑问，请在线咨询，有专业老师随时为你服务。