2023-07-27：最長可整合子數(shù)組的長度， 數(shù)組中的數(shù)字排序之后，相鄰兩數(shù)的差值是1，
2023-07-27：最長可整合子數(shù)組的長度，
數(shù)組中的數(shù)字排序之后，相鄰兩數(shù)的差值是1，
這種數(shù)組就叫可整合數(shù)組。
給定一個數(shù)組，求最長可整合子數(shù)組的長度。
答案2023-07-27：
算法maxLen的過程如下：
1.檢查輸入數(shù)組是否為空，如果為空，則返回0，表示最長可整合子數(shù)組長度為0。
2.初始化長度為1的最長可整合子數(shù)組長度為ans。
3.創(chuàng)建一個空的set容器，用于記錄數(shù)組中的元素是否已經(jīng)存在。
4.開始遍歷輸入數(shù)組，從start = 0開始。每次迭代，重置set為空。
5.初始化minVal和maxVal為arr[start]。
6.將arr[start]添加到set中，表示該元素已經(jīng)存在。
7.開始從start+1位置向后遍歷數(shù)組，每次迭代的終止條件是end < len(arr)。
8.如果arr[end]在set中已經(jīng)存在，表示遇到了重復元素，跳出循環(huán)。
9.將arr[end]添加到set中，表示該元素已經(jīng)存在。
10.更新minVal和maxVal，如果arr[end]比minVal小，則更新minVal為arr[end]；如果arr[end]比maxVal大，則更新maxVal為arr[end]。
11.檢查當前子數(shù)組是否為可整合數(shù)組，即判斷maxVal和minVal之間的差值是否等于end-start。
12.如果當前子數(shù)組為可整合數(shù)組，更新ans為當前子數(shù)組長度和ans中較大的值。
13.返回最長可整合子數(shù)組長度ans。
算法right的過程如下：
1.檢查輸入數(shù)組是否為空，如果為空，則返回0，表示最長可整合子數(shù)組長度為0。
2.初始化ans為0，用于記錄最長可整合子數(shù)組的長度。
3.創(chuàng)建一個和輸入數(shù)組相同長度的輔助數(shù)組help。
4.開始從左邊界l開始遍歷數(shù)組，每次迭代，右邊界r從l開始向右遍歷數(shù)組。
5.將arr[l:r+1]拷貝到輔助數(shù)組help的對應位置。
6.對help數(shù)組的切片help[l:r+1]進行排序，將切片中的元素按從小到大的順序排列。
7.檢查排序后的help數(shù)組是否符合可整合數(shù)組的條件，即判斷help數(shù)組中相鄰元素之間的差值是否為1。
8.如果help數(shù)組滿足可整合數(shù)組條件，更新ans為當前子數(shù)組長度和ans中較大的值。
9.返回最長可整合子數(shù)組長度ans。
算法maxLen的時間復雜度和空間復雜度分別為：
時間復雜度：
??最壞情況下，需要遍歷輸入數(shù)組中的每個元素，所以時間復雜度為O(n)，其中n是輸入數(shù)組的長度。
空間復雜度：
??使用了一個set容器來存儲元素，所以空間復雜度為O(n)，其中n是輸入數(shù)組的長度。
算法right的時間復雜度和空間復雜度分別為：
時間復雜度：
??最壞情況下，需要對每個子數(shù)組進行排序，對于長度為m的子數(shù)組，排序的時間復雜度為O(mlogm)。
??因此，整個算法的時間復雜度為O(n^2 log n)，其中n是輸入數(shù)組的長度。
空間復雜度：
??使用了一個輔助數(shù)組help存儲子數(shù)組的拷貝，所以空間復雜度為O(n)，其中n是輸入數(shù)組的長度。
go完整代碼如下：
package?main
import?(
????"fmt"
????"math"
????"math/rand"
????"sort"
)
func?maxLen(arr?[]int)?int?{
????if?arr?==?nil?||?len(arr)?==?0?{
????????return?0
????}
????ans?:=?1
????set?:=?make(map[int]bool)
????for?start?:=?0;?start?<?len(arr);?start++?{
????????set?=?make(map[int]bool)
????????minVal?:=?arr[start]
????????maxVal?:=?arr[start]
????????set[arr[start]]?=?true
????????for?end?:=?start?+?1;?end?<?len(arr);?end++?{
????????????if?set[arr[end]]?{
????????????????break
????????????}
????????????set[arr[end]]?=?true
????????????if?arr[end]?<?minVal?{
????????????????minVal?=?arr[end]
????????????}
????????????if?arr[end]?>?maxVal?{
????????????????maxVal?=?arr[end]
????????????}
????????????if?maxVal-minVal?==?end-start?{
????????????????ans?=?int(math.Max(float64(end-start+1),?float64(ans)))
????????????}
????????}
????}
????return?ans
}
func?right(arr?[]int)?int?{
????if?arr?==?nil?||?len(arr)?==?0?{
????????return?0
????}
????n?:=?len(arr)
????ans?:=?0
????help?:=?make([]int,?n)
????for?l?:=?0;?l?<?n;?l++?{
????????for?r?:=?l;?r?<?n;?r++?{
????????????copy(help[l:r+1],?arr[l:r+1])
????????????sort.Ints(help[l?:?r+1])
????????????ok?:=?true
????????????for?i?:=?l?+?1;?i?<=?r;?i++?{
????????????????if?help[i-1]+1?!=?help[i]?{
????????????????????ok?=?false
????????????????????break
????????????????}
????????????}
????????????if?ok?{
????????????????ans?=?int(math.Max(float64(ans),?float64(r-l+1)))
????????????}
????????}
????}
????return?ans
}
func?randomArray(n,?v?int)?[]int?{
????arr?:=?make([]int,?n)
????for?i?:=?0;?i?<?n;?i++?{
????????arr[i]?=?rand.Intn(v)?+?1
????}
????return?arr
}
func?main()?{
????N?:=?100
????V?:=?50
????testTimes?:=?10000
????fmt.Println("測試開始")
????for?i?:=?0;?i?<?testTimes;?i++?{
????????n?:=?rand.Intn(N)
????????arr?:=?randomArray(n,?V)
????????ans1?:=?maxLen(arr)
????????ans2?:=?right(arr)
????????if?ans1?!=?ans2?{
????????????fmt.Println("出錯了!")
????????}
????}
????fmt.Println("測試結(jié)束")
}
c++完整代碼如下：
using?namespace?std;
int?maxLen(vector<int>&?arr)?{
????if?(arr.empty())?{
????????return?0;
????}
????int?ans?=?1;
????unordered_set<int>?set;
????for?(int?start?=?0;?start?<?arr.size();?start++)?{
????????set.clear();
????????int?minVal?=?arr[start];
????????int?maxVal?=?arr[start];
????????set.insert(arr[start]);
????????for?(int?end?=?start?+?1;?end?<?arr.size();?end++)?{
????????????if?(set.find(arr[end])?!=?set.end())?{
????????????????break;
????????????}
????????????set.insert(arr[end]);
????????????minVal?=?min(minVal,?arr[end]);
????????????maxVal?=?max(maxVal,?arr[end]);
????????????if?(maxVal?-?minVal?==?end?-?start)?{
????????????????ans?=?max(ans,?end?-?start?+?1);
????????????}
????????}
????}
????return?ans;
}
int?right(vector<int>&?arr)?{
????if?(arr.empty())?{
????????return?0;
????}
????int?n?=?arr.size();
????int?ans?=?0;
????vector<int>?help(n);
????for?(int?l?=?0;?l?<?n;?l++)?{
????????for?(int?r?=?l;?r?<?n;?r++)?{
????????????for?(int?i?=?l;?i?<=?r;?i++)?{
????????????????help[i]?=?arr[i];
????????????}
????????????sort(help.begin()?+?l,?help.begin()?+?r?+?1);
????????????bool?ok?=?true;
????????????for?(int?i?=?l?+?1;?i?<=?r;?i++)?{
????????????????if?(help[i?-?1]?+?1?!=?help[i])?{
????????????????????ok?=?false;
????????????????????break;
????????????????}
????????????}
????????????if?(ok)?{
????????????????ans?=?max(ans,?r?-?l?+?1);
????????????}
????????}
????}
????return?ans;
}
vector<int>?randomArray(int?n,?int?v)?{
????vector<int>?ans(n);
????for?(int?i?=?0;?i?<?n;?i++)?{
????????ans[i]?=?rand()?%?v?+?1;
????}
????return?ans;
}
int?main()?{
????int?N?=?100;
????int?V?=?50;
????int?testTimes?=?10000;
????cout?<<?"測試開始"?<<?endl;
????for?(int?i?=?0;?i?<?testTimes;?i++)?{
????????int?n?=?rand()?%?N;
????????vector<int>?arr?=?randomArray(n,?V);
????????int?ans1?=?maxLen(arr);
????????int?ans2?=?right(arr);
????????if?(ans1?!=?ans2)?{
????????????cout?<<?"出錯了!"?<<?endl;
????????}
????}
????cout?<<?"測試結(jié)束"?<<?endl;
????return?0;
}
