longest-consecutive-sequence
xiaowei520 · · 1055 次点击 · · 开始浏览https://leetcode.com/problems/longest-consecutive-sequence/
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(_n_) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
解题思路:
1.利用hashmap 存储
2.每次存储的时候判断 n-1 n+1 即当前元素的前后两个位置,是否有元素,
有的话将对应位置的数据++,然后将n 赋值为调整后的指针。
最后就能得到一个hashmap存储的指针地址
3.在每一步得到n 的大小都与max 进行比较。调整赋值。
该思路能得到一个完整的hashmap key =>pointer 。更适合拓展
以下是实现的代码
func longestConsecutive(nums []int) int {
globalN := map[int]*int{}
max := 0
for _, v := range nums {
if globalN[v] != nil {
continue
}
//左侧非nil
if globalN[v-1] != nil && globalN[v+1] == nil {
//指针地址偏移
*globalN[v-1] = *globalN[v-1] + 1
globalN[v] = globalN[v-1] //以左侧指针为准
} else if globalN[v+1] != nil && globalN[v-1] == nil {
*globalN[v+1] = *globalN[v+1] + 1
globalN[v] = globalN[v+1] //以右侧指针为准
} else if globalN[v+1] != nil && globalN[v-1] != nil {
//左侧的全跟上
*globalN[v-1] = *globalN[v-1] + 1 + *globalN[v+1]
//全部以左侧为准,所以修改的是最右侧的 为左侧指针
globalN[v+*globalN[v+1]] = globalN[v-1] //右侧指针和左侧一样
globalN[v] = globalN[v-1] //中间和左侧 左侧一样都行
} else {
s := 1
globalN[v] = &s
}
if *globalN[v] > max {
max = *globalN[v]
}
}
return max
}有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
https://leetcode.com/problems/longest-consecutive-sequence/
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(_n_) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
解题思路:
1.利用hashmap 存储
2.每次存储的时候判断 n-1 n+1 即当前元素的前后两个位置,是否有元素,
有的话将对应位置的数据++,然后将n 赋值为调整后的指针。
最后就能得到一个hashmap存储的指针地址
3.在每一步得到n 的大小都与max 进行比较。调整赋值。
该思路能得到一个完整的hashmap key =>pointer 。更适合拓展
以下是实现的代码
func longestConsecutive(nums []int) int {
globalN := map[int]*int{}
max := 0
for _, v := range nums {
if globalN[v] != nil {
continue
}
//左侧非nil
if globalN[v-1] != nil && globalN[v+1] == nil {
//指针地址偏移
*globalN[v-1] = *globalN[v-1] + 1
globalN[v] = globalN[v-1] //以左侧指针为准
} else if globalN[v+1] != nil && globalN[v-1] == nil {
*globalN[v+1] = *globalN[v+1] + 1
globalN[v] = globalN[v+1] //以右侧指针为准
} else if globalN[v+1] != nil && globalN[v-1] != nil {
//左侧的全跟上
*globalN[v-1] = *globalN[v-1] + 1 + *globalN[v+1]
//全部以左侧为准,所以修改的是最右侧的 为左侧指针
globalN[v+*globalN[v+1]] = globalN[v-1] //右侧指针和左侧一样
globalN[v] = globalN[v-1] //中间和左侧 左侧一样都行
} else {
s := 1
globalN[v] = &s
}
if *globalN[v] > max {
max = *globalN[v]
}
}
return max
}