2021年7月1日：如何计算数组中连续数字序列的最大长度？
- 内容介绍
- 文章标签
- 相关推荐
本文共计373个文字，预计阅读时间需要2分钟。
pythondef longest_consecutive(arr): arr.sort() longest=0 current=1 for i in range(1, len(arr)): if arr[i]==arr[i - 1] + 1: current +=1 else: longest=max(longest, current) current=1 longest=max(longest, current) return longest
输入arr=[100, 4, 1, 20, 3, 2, 50]输出print(longest_consecutive(arr))
2021-07-01：最长连续序列。一个未排序的arr，找出数字连续的最长序列的长度。输入：[100,4,1,20,3,2,50]，输出：4。解释：最长数字连续序列是[1,2,3,4]，所以长度是4。
福大大 答案2021-07-01：
连续区间头表，map1[5]=3，是5,6,7。
连续区间尾表，map2[5]=3，是3,4,5。
求map1中的value最大值，就是需要的返回值。
时间复杂度：O(N)。
空间复杂度：O(N)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
arr := []int{100, 4, 1, 20, 3, 2, 50}
ret := longestConsecutive(arr)
fmt.Println(ret)
}
func longestConsecutive(nums []int) int {
map0 := make(map[int]int)
ans := 0
for _, num := range nums {
if _, ok := map0[num]; !ok {
map0[num] = 1
preLen := 0
posLen := 0
if _, ok := map0[num-1]; ok {
preLen = map0[num-1]
}
if _, ok := map0[num+1]; ok {
posLen = map0[num+1]
}
all := preLen + posLen + 1
map0[num-preLen] = all
map0[num+posLen] = all
ans = getMax(ans, all)
}
}
return ans
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
执行结果如下：
左神java代码
本文共计373个文字，预计阅读时间需要2分钟。
pythondef longest_consecutive(arr): arr.sort() longest=0 current=1 for i in range(1, len(arr)): if arr[i]==arr[i - 1] + 1: current +=1 else: longest=max(longest, current) current=1 longest=max(longest, current) return longest
输入arr=[100, 4, 1, 20, 3, 2, 50]输出print(longest_consecutive(arr))
2021-07-01：最长连续序列。一个未排序的arr，找出数字连续的最长序列的长度。输入：[100,4,1,20,3,2,50]，输出：4。解释：最长数字连续序列是[1,2,3,4]，所以长度是4。
福大大 答案2021-07-01：
连续区间头表，map1[5]=3，是5,6,7。
连续区间尾表，map2[5]=3，是3,4,5。
求map1中的value最大值，就是需要的返回值。
时间复杂度：O(N)。
空间复杂度：O(N)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
arr := []int{100, 4, 1, 20, 3, 2, 50}
ret := longestConsecutive(arr)
fmt.Println(ret)
}
func longestConsecutive(nums []int) int {
map0 := make(map[int]int)
ans := 0
for _, num := range nums {
if _, ok := map0[num]; !ok {
map0[num] = 1
preLen := 0
posLen := 0
if _, ok := map0[num-1]; ok {
preLen = map0[num-1]
}
if _, ok := map0[num+1]; ok {
posLen = map0[num+1]
}
all := preLen + posLen + 1
map0[num-preLen] = all
map0[num+posLen] = all
ans = getMax(ans, all)
}
}
return ans
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
执行结果如下：
左神java代码