2023-07-27：最长可整合子数组的长度，
数组中的数字排序之后，相邻两数的差值是 1，
这种数组就叫可整合数组。
给定一个数组，求最长可整合子数组的长度。
答案 2023-07-27：
算法 maxLen 的过程如下：
1.检查输入数组是否为空，如果为空，则返回 0，表示最长可整合子数组长度为 0。
2.初始化长度为 1 的最长可整合子数组长度为 ans。
3.创建一个空的 set 容器，用于记录数组中的元素是否已经存在。
4.开始遍历输入数组，从 start = 0 开始。每次迭代，重置 set 为空。
5.初始化 minVal 和 maxVal 为 arr[start]。
6.将 arr[start]添加到 set 中，表示该元素已经存在。
7.开始从 start+1 位置向后遍历数组，每次迭代的终止条件是 end < len(arr)。
8.如果 arr[end]在 set 中已经存在，表示遇到了重复元素，跳出循环。
9.将 arr[end]添加到 set 中，表示该元素已经存在。
10.更新 minVal 和 maxVal，如果 arr[end]比 minVal 小，则更新 minVal 为 arr[end]；如果 arr[end]比 maxVal 大，则更新 maxVal 为 arr[end]。
11.检查当前子数组是否为可整合数组，即判断 maxVal 和 minVal 之间的差值是否等于 end-start。
12.如果当前子数组为可整合数组，更新 ans 为当前子数组长度和 ans 中较大的值。
13.返回最长可整合子数组长度 ans。
算法 right 的过程如下：
1.检查输入数组是否为空，如果为空，则返回 0，表示最长可整合子数组长度为 0。
2.初始化 ans 为 0，用于记录最长可整合子数组的长度。
3.创建一个和输入数组相同长度的辅助数组 help。
4.开始从左边界 l 开始遍历数组，每次迭代，右边界 r 从 l 开始向右遍历数组。
5.将 arr[l:r+1]拷贝到辅助数组 help 的对应位置。
6.对 help 数组的切片 help[l:r+1]进行排序，将切片中的元素按从小到大的顺序排列。
7.检查排序后的 help 数组是否符合可整合数组的条件，即判断 help 数组中相邻元素之间的差值是否为 1。
8.如果 help 数组满足可整合数组条件，更新 ans 为当前子数组长度和 ans 中较大的值。
9.返回最长可整合子数组长度 ans。
算法 maxLen 的时间复杂度和空间复杂度分别为：
时间复杂度：
空间复杂度：
算法 right 的时间复杂度和空间复杂度分别为：
时间复杂度：
空间复杂度：
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("测试结束")}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>#include <algorithm>#include <unordered_set>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 << "测试结束" << endl; return 0;}
复制代码
评论