如果一個(gè)數(shù)組在排序之后，每相鄰兩個(gè)數(shù)差的絕對(duì)值都為1，則該數(shù)組為可整合數(shù)組。例如：[5,3,4,6，2]排序之后為[2,3,4,5,6],符合每相鄰兩個(gè)數(shù)差的絕對(duì)值都為1，所以這個(gè)數(shù)組為可整合數(shù)組。
給定一個(gè)整型數(shù)組arr，要求返回其中最大可整合數(shù)組的長(zhǎng)度。例如，[5,5,3,2,6,4,3]的最大整合子數(shù)組為[5,3,2,6,4]，所以返回5.
時(shí)間復(fù)雜度高但容易理解的做法。對(duì)arr中的每一個(gè)子數(shù)組arr[i……j]（0<=i<=j<=N-1），都驗(yàn)證一下是否符合可整合數(shù)組的定義，也就是把a(bǔ)rr[i……j]排序一下，看是否依次遞增且每次遞增1.然后在所有符合整合數(shù)組定義的子數(shù)組中，記錄最大的那個(gè)長(zhǎng)度，返回即可。需要注意的是，在考查每一個(gè)arr[i……j]是否符合可整合數(shù)組定義的時(shí)候，都得把a(bǔ)rr[i……j]單獨(dú)復(fù)制成一個(gè)新的數(shù)組，然后把這個(gè)新的數(shù)組排序、驗(yàn)證，而不能直接改變arr中元素的順序。大體過(guò)程如下：依次考查每一個(gè)子數(shù)組arr[i……j](0<=i<=j<=N-1),一共有O（N^2）個(gè)。2.對(duì)每一個(gè)子數(shù)組arr[i……j],復(fù)制成一個(gè)新的數(shù)組，記為newArr，把newArr排序，然后驗(yàn)證是否符合可整合數(shù)組的定義，這一步代價(jià)為O（NlogN）。3.步驟2中符合條件的、最大的那個(gè)子數(shù)組的長(zhǎng)度就是結(jié)果。
具體過(guò)程看如下代碼中的getLIL1方法，時(shí)間復(fù)雜度為O（N^2）*O(NlogN)-O(N^3logN).
第一種方法嚴(yán)格按照定義來(lái)驗(yàn)證每一個(gè)子數(shù)組是否是可整合數(shù)組，但是驗(yàn)證可整合數(shù)組真的需要如此麻煩嗎？有沒(méi)有更好的方法來(lái)加速驗(yàn)證過(guò)程？這也是下面要提供方法的核心。判斷一個(gè)數(shù)組是否是可整合數(shù)組還可以用以下方法來(lái)判斷，一個(gè)數(shù)組中如果沒(méi)有重復(fù)元素，并且如果最大值減去最小值，再加1的結(jié)果等于元素個(gè)數(shù)（max-min+1==元素個(gè)數(shù)），那么這個(gè)數(shù)組就是可整合數(shù)組。比如[3,2,5,6,4]，max-min+1=6-2+1=5==元素個(gè)數(shù)，所以這個(gè)數(shù)組是可整合數(shù)組。這樣，驗(yàn)證每一個(gè)子數(shù)組是否是可整合數(shù)組的時(shí)間復(fù)雜度可以從第一種方法的O（NlogN）加速至O（1），整個(gè)過(guò)程的時(shí)間復(fù)雜度就可加速到O（N^2），具體請(qǐng)參看如下代碼中的getLIL2方法。
算法與數(shù)據(jù)結(jié)構(gòu)--最長(zhǎng)的可整合子數(shù)組的長(zhǎng)度的普通解法和進(jìn)階解法（java實(shí)現(xiàn)）
以上就是長(zhǎng)沙達(dá)內(nèi)教育Java培訓(xùn)機(jī)構(gòu)小編介紹的“Java培訓(xùn)教程：Java數(shù)組長(zhǎng)度的普通解法和進(jìn)階解法”的內(nèi)容，希望對(duì)大家有幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢，有專(zhuān)業(yè)老師隨時(shí)為你服務(wù)。
