热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【leetcode】LongestConsecutiveSequence(hard)☆

Givenanunsortedarrayofintegers,findthelengthofthelongestconsecutiveelementssequence.Forexa

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

思路:先把大神的方法亮出来

use a hash map to store boundary information of consecutive sequence for each element; there 4 cases when a new element i reached:

1) neither i+1 nor i-1 has been seen: m[i]=1;

2) both i+1 and i-1 have been seen: extend m[i+m[i+1]] and m[i-m[i-1]] to each other;

3) only i+1 has been seen: extend m[i+m[i+1]] and m[i] to each other;

4) only i-1 has been seen: extend m[i-m[i-1]] and m[i] to each other.

int longestConsecutive(vector<int> &num) {
    unordered_map<int, int> m;
    int r = 0;
    for (int i : num) {
        if (m[i]) continue; //跳过重复
        r = max(r, m[i] = m[i + m[i + 1]] = m[i - m[i - 1]] = m[i + 1] + m[i - 1] + 1); //如果新的数字把左右连起来了,则把该连起来的序列的第一个数m[i - m[i - 1]]和最后一个数字m[i + m[i + 1]] 设为新的长度!
    }
    return r;
}

下面是我自己写的,可谓血与泪的历史。

首先O(n)表示一定不能排序, 那如何获得左右邻接的信息呢。 肯定要用hash了。结果花了2个小时,写了一个超复杂的代码。虽然AC,但是.......唉...................................................

int longestConsecutive(vector<int> &num) {
        //去重复
        unordered_set<int> s;
        for(int i = 0; i )
        {
            if(s.find(num[i]) == s.end())
                s.insert(num[i]);
            else
                num.erase(num.begin() + (i--));
        }
        
        int maxlen = 0;
        unordered_map<int, int> first; //记录每个连续序列的第一个数字在record中的哪个位置
        unordered_map<int, int> last; //记录每个连续序列的最后一个数字在record中的哪个位置
        vectorint>> record; //记录每个连续序列的第一个数字和最后一个数字是什么
        for(int i = 0; i )
        {
            int pre, post;
            unordered_map<int, int>::iterator f = first.find(num[i] + 1);
            unordered_map<int, int>::iterator l = last.find(num[i] - 1);
            if(f != first.end() && l != last.end())
            {
                pre = l->second;
                post = f->second;
                //修改hash表
                last.erase(record[pre][1]);
                first.erase(record[post][0]);
                last[record[post][1]] = pre;
                //修改记录的区间
                record[pre][1] = record[post][1];
                maxlen = (maxlen > record[pre][1] - record[pre][0] + 1) ? maxlen :  record[pre][1] - record[pre][0] + 1;
                record[post].clear();
            }
            else if(f != first.end())
            {
                post = f->second;
                //修改hash
                first.erase(record[post][0]);
                first[num[i]] = post;
                //修改区间
                record[post][0] = num[i];
                maxlen = (maxlen > record[post][1] - record[post][0] + 1) ? maxlen :  record[post][1] - record[post][0] + 1;
            }
            else if(l != last.end())
            {
                pre = l->second;
                last.erase(record[pre][0]);
                last[num[i]] = pre;

                record[pre][1] = num[i];
                maxlen = (maxlen > record[pre][1] - record[pre][0] + 1) ? maxlen :  record[pre][1] - record[pre][0] + 1;
            }
            else
            {
                record.push_back(vector<int>(2, num[i]));
                first[num[i]] = record.size() - 1;
                last[num[i]] = record.size() - 1;
                maxlen = (maxlen > 1) ? maxlen : 1;
            }
        }
        return maxlen;
    }

【leetcode】Longest Consecutive Sequence(hard)☆


推荐阅读
  • 本文详细介绍了IBM DB2数据库在大型应用系统中的应用,强调其卓越的可扩展性和多环境支持能力。文章深入分析了DB2在数据利用性、完整性、安全性和恢复性方面的优势,并提供了优化建议以提升其在不同规模应用程序中的表现。 ... [详细]
  • QUIC协议:快速UDP互联网连接
    QUIC(Quick UDP Internet Connections)是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP,并结合了TLS级别的安全性,提供了更高效、更可靠的互联网通信方式。 ... [详细]
  • 深入理解OAuth认证机制
    本文介绍了OAuth认证协议的核心概念及其工作原理。OAuth是一种开放标准,旨在为第三方应用提供安全的用户资源访问授权,同时确保用户的账户信息(如用户名和密码)不会暴露给第三方。 ... [详细]
  • 本文探讨了如何通过最小生成树(MST)来计算严格次小生成树。在处理过程中,需特别注意所有边权重相等的情况,以避免错误。我们首先构建最小生成树,然后枚举每条非树边,检查其是否能形成更优的次小生成树。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • Windows服务与数据库交互问题解析
    本文探讨了在Windows 10(64位)环境下开发的Windows服务,旨在定期向本地MS SQL Server (v.11)插入记录。尽管服务已成功安装并运行,但记录并未正确插入。我们将详细分析可能的原因及解决方案。 ... [详细]
  • 深入理解 Oracle 存储函数:计算员工年收入
    本文介绍如何使用 Oracle 存储函数查询特定员工的年收入。我们将详细解释存储函数的创建过程,并提供完整的代码示例。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 本文详细介绍如何使用Python进行配置文件的读写操作,涵盖常见的配置文件格式(如INI、JSON、TOML和YAML),并提供具体的代码示例。 ... [详细]
  • CSS 布局:液态三栏混合宽度布局
    本文介绍了如何使用 CSS 实现液态的三栏布局,其中各栏具有不同的宽度设置。通过调整容器和内容区域的属性,可以实现灵活且响应式的网页设计。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 深入理解Cookie与Session会话管理
    本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息,以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制,解释其原理及应用场景。 ... [详细]
  • 数据库内核开发入门 | 搭建研发环境的初步指南
    本课程将带你从零开始,逐步掌握数据库内核开发的基础知识和实践技能,重点介绍如何搭建OceanBase的开发环境。 ... [详细]
  • 数据管理权威指南:《DAMA-DMBOK2 数据管理知识体系》
    本书提供了全面的数据管理职能、术语和最佳实践方法的标准行业解释,构建了数据管理的总体框架,为数据管理的发展奠定了坚实的理论基础。适合各类数据管理专业人士和相关领域的从业人员。 ... [详细]
  • 深入理解 SQL 视图、存储过程与事务
    本文详细介绍了SQL中的视图、存储过程和事务的概念及应用。视图为用户提供了一种灵活的数据查询方式,存储过程则封装了复杂的SQL逻辑,而事务确保了数据库操作的完整性和一致性。 ... [详细]
author-avatar
个信2602926933
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有