首页 > 其他分享 >最长连续序列

最长连续序列

时间:2022-10-26 21:37:34浏览次数:272  
标签:set nums int res remove 连续 序列 data 最长


题目来源

​Longest Consecutive Sequence​

问题描述

给定一个未排序的整数数组,找出最长连续序列的长度。

例如,
给出 [100, 4, 200, 1, 3, 2],
这个最长的连续序列是 [1, 2, 3, 4]。返回所求长度: 4。

要求你的算法复杂度为 O(n)。

解决方案

Java

class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (Integer n : nums)
set.add(n);

int res = 0;
int p = 0;

for(int data: nums) { //遍历原数组
p = 1;
set.remove(data);
for (int i = data-1; set.contains(i); i--) {
set.remove(i);
//移除hashset中已经求结果的数据(如[1,2,3]中的1,2,3的最大序列都是3),从而加快contains等函数
p++;
}
for (int i = data+1; set.contains(i); i++) {
set.remove(i);
p++;
}
res = res > p ? res : p;
}
return

python

class Solution:
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res=0
s=set(nums)
for i in nums:
data=i
p=1
for _ in range(len(s)):
if(data-1 in s):
p+=1
data-=1
s.remove(data)
data=i
for _ in range(len(s)):
if (data+1 in s):
p+=1
data+=1
s.remove(data)
res=max(res,p)
return

说明:在集合迭代过程中不允许对集合中的数据进行更改,比如python代码第三行中 ​​for i in nums:​​​改为​​for i in s:​​​会报错​​RuntimeError: Set changed size during iteration​​。


标签:set,nums,int,res,remove,连续,序列,data,最长
From: https://blog.51cto.com/u_15847885/5798568

相关文章

  • 最长公共子序列问题
    最长公共子序列问题作者:Grey原文地址:博客园:最长公共子序列问题CSDN:最长公共子序列问题题目描述给定两个字符串text1和text2,返回这两个字符串的最长公共子序列的......
  • 最长非递减子序列--顺丰2020校招笔试题
    n的范围是[0,100000]DP版本(O(n^2))时间复杂度(LTE):#include<cstdio>#include<iostream>#include<algorithm>usingnamespacestd;#defineN100intmain(){intA[N],dp[N......
  • 手撕代码——最长不包含重复字符的字符串长度
    3. LongestSubstringWithoutRepeatingCharactersMedium6059348FavoriteShareGivenastring,findthelengthofthe longestsubstring withoutrepeatingcharact......
  • 最长递增子序列
    题目描述给定一个序列An=a1,a2, ...,an,找出最长的子序列使得对所有i<j,ai<aj。求出这个子序列的长度输入描述:输入的序列输出描述:最长递增子序列的长度示......
  • 求两个字符串的最长公共子字符串长度
    题目描述给定两个字符串,请编写代码,输出最长公共子串(LongestCommonSubstring),是指两个字符串中的最长的公共子串,要求子串一定是连续。输入描述:文本格式,2个非空字符串(字母......
  • 连续子区间的和大于等于某一个数
    题目描述小M给你一串含有c个正整数的数组, 想让你帮忙求出有多少个下标的连续区间, 它们的和大于等于x。输入描述:第一行两个整数cx(0<c<=1000000,0<=x<=100000......
  • 最长对称子字符串
    题目描述给定一个字符串(数字或大小写字母),找出最长的对称的子串(如有多个,输出任意一个)。例如:输入:“abbaad”输出:“abba”输入描述:字符串输出描述:字符串示例1输入复制......
  • .Net内置JSON序列化中文问题
    今天在用System.Text.Json序列化的时候遇到了中文序列化的一个问题,示例如下:JsonSerializer.Serialize(new{Name="你好"});预期结果是:{"Name":"你好"},但得到结果如下......
  • R语言用FNN-LSTM假近邻长短期记忆人工神经网络模型进行时间序列深度学习预测4个案例|
    全文链接:tecdat.cn/?p=23792在最近的一篇文章中,我们展示了一个LSTM模型,通过假近邻(FNN)损失进行正则化,可以用来重建一个非线性动态系统 ( 点击文末“阅读原文”获取完整代......
  • 最长公共子串
    ​​参考LCS通解​​题目描述牛牛拿到了一个藏宝图,顺着藏宝图的指示,牛牛发现了一个藏宝盒,藏宝盒上有一个机关,机关每次会显示两个字符串s和t,根据古老的传说,牛牛需要每次都......