LeetCode第128题:最长连续序列

作者 the7
发布于 2020年03月05日
评论 0
浏览 223

给定一个未排序的整数数组,找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4

解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

原文链接: https://leetcode-cn.com/problems/longest-consecutive-sequence/

解题

  • 用一个字典存数组中每个数字的当前连续最长长度
  • 如果已经遍历过的则跳过
  • 若从未遍历过
    • 取左右相邻的数字
    • 当前最大即为 左边存的值 + 右边存的值 + 1
    • 更新两端的值(因为在循环中只会用到两端的值)
static int LongestConsecutive(int[] nums)
{
    if (nums.Length <= 1) return nums.Length;
    var dict = new Dictionary<int,int>();
    var max = 1;
    for (var i = 0; i < nums.Length; i++)
    {
        var num = nums[i];
        if (!dict.ContainsKey(num))
        {
            var left = num - 1;
            var leftValue = 0;
            
            var right = num + 1;
            var rightValue = 0;
            
            if (dict.ContainsKey(left)) //取左侧存值
                leftValue = dict[left];
            
            if (dict.ContainsKey(right)) //取右侧存值
                rightValue = dict[right];

            var value = leftValue + rightValue + 1;
            if (value > max) max = value;
            dict[num] = value;
            if (leftValue>0)
                dict[num-leftValue]=value; //更新最左端的值
            if (rightValue>0)
                dict[num+rightValue] = value; //更新最右段的值
        }
    }
	return max;
}

执行结果

0条评论

请先登录后发表评论
提交评论
标签云
css (1) less calc (1) C# (4) C#进制转换 (1) asp.net core (8) Authentication (1) 注销 (1) 登录 (1) 验证 (1) scroll-view (1) 微信小程序 (4) 滚动到底部 (1) StackExchange.Redis (1) google (1) 百度 (1) nginx (2) 大文件 (2) 微信小程序c#解密 (1) 微信小程序获取手机号 (1) openid (1) session_key (1) CDN (1) URL鉴权 (1) 阿里云 (1) async (1) await (1) 禁止下拉上滑效果 (1) Index类型 (1) Range类型 (1) dontent publish (1) dotnet publish在线生成器 (1) System.DrawingCore.GDIPlus报错 (1) centos (1) 中文字体 (1) SqlBulkCopy (1) SqlSugar (1) JWT (5) 认证 (3) RSA JWT (1) 非对称加密 (1) 写信 (1) 见字如面 (1) 优化建议 (2) 正确操作字符串 (1) Java (1) JWT退出 (1) RefreshToken (1) .NET Core网站开发框架 (1) Moz (3) 墨子 (1) JSON.NET (1) Newtonsoft (1) System.Text.Json (1) 自定义后台路径 (1) .netcore (1) quartz (2) 作业调度框架 (1) 作业调度 (1) 定时任务 (1) exception (1) 异常处理 (1) HttpClient (1) IHttpClientFactory (1) RDM (1) Redis (1) Redis Desktop Manager (1) RedisDesktopManager (1) linux (1) mac (1) windows (1) Could not get any response (1) postman (1) leetcode (2) 力扣 (1) 回文字符串 (1) 面试刷题 (1) centos7 (1) php安装 (1) 网易云插件 (1) 马甲App (1) Discuz插件 (1) 网易云音乐 (1) Blazor (1) 五子棋 (1) c#解题 (1) 最长连续序列 (1) Swagger (1) 在线文档 (1) blob (1) mp4 (1) 视频 (1) big file (1) 上传 (1) s (1) Azure (1) Azure Key Vault (1) Configuration (1) 密钥保管库 (1) Dapper安装 (1) Dapper是什么 (1) Dapper连接Mysql (1) Dapper连接SqlServer (1) dapper (1)