longest-consecutive-sequence

xiaowei520 · · 47 次点击 · · 开始浏览    

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
}

本文来自:Segmentfault

感谢作者:xiaowei520

查看原文:longest-consecutive-sequence

入群交流(和以上内容无关):Go中文网 QQ 交流群:729884609 或加微信入微信群:274768166 备注:入群;关注公众号:Go语言中文网

47 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传