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的时间复杂度和空间复杂度分别为：
时间复杂度：
最坏情况下，需要遍历输入数组中的每个元素，所以时间复杂度为O(n)，其中n是输入数组的长度。
空间复杂度：
使用了一个set容器来存储元素，所以空间复杂度为O(n)，其中n是输入数组的长度。
算法right的时间复杂度和空间复杂度分别为：
时间复杂度：
最坏情况下，需要对每个子数组进行排序，对于长度为m的子数组，排序的时间复杂度为O(mlogm)。
因此，整个算法的时间复杂度为O(n^2 log n)，其中n是输入数组的长度。
空间复杂度：
使用了一个辅助数组help存储子数组的拷贝，所以空间复杂度为O(n)，其中n是输入数组的长度。
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
#include
#include
#include
using namespace std;
int maxLen(vector
if (arr.empty()) {
return 0;
}
int ans = 1;
unordered_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
if (arr.empty()) {
return 0;
}
int n = arr.size();
int ans = 0;
vector
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
vector
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 ans1 = maxLen(arr);
int ans2 = right(arr);
if (ans1 != ans2) {
cout << "出错了!" << endl;
}
}
cout << "测试结束" << endl;
return 0;
}
好文链接
发表评论