it培训机构网站开发,眼前一亮的公司名,做钻石资讯网站,网游开发培训题目描述
给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
出处
思路
此题可用带排序的哈希表#xff0c;先构建哈希表#xff0…题目描述
给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
出处
思路
此题可用带排序的哈希表先构建哈希表然后遍历哈希表维护一个工作数和一个最长记录初始值均为1若相邻两个哈希表项的key相差1则工作数否则视情况更新最长记录并把工作数归1。 value不起作用题目无需考虑存在多个相同key的问题。
代码
class Solution {
public:mapint, int hash;int longestConsecutive(vectorint nums) {if(nums.empty())return 0;for(auto i : nums){hash[i] i;}int max1,tmp1;auto prehash.begin();auto ithash.begin();while(it!hash.end()){if(it-firstpre-first1) {//若连续tmp;if (tmp max)max tmp;}elsetmp1;pre;it;}return max;}
};
