做h5免费的网站有,买cms做网站,爱站网关键词查询网站的工具,百度竞价给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1#xff1a;
输入#xff1a;nums [100,4,200,1,3,2]
输出#xff1a;4
解… 给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1
输入nums [100,4,200,1,3,2]
输出4
解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2
输入nums [0,3,7,2,5,8,4,6,0,1]
输出9提示
0 nums.length 105-109 nums[i] 109
题目链接128. 最长连续序列 - 力扣LeetCode 暴力破解 class Solution {
public:int longestConsecutive(vectorint nums) {setint nums_set; //无序存储基本操作的复杂度大多为常数级for(const int num:nums){nums_set.insert(num);}int longestStreak 0;auto it nums_set.begin();int last_num *it;int currentStreak 1;it ;for (; it ! nums_set.end(); it){if((*it) (last_num 1)){currentStreak;}else{currentStreak 1;}longestStreak longestStreak currentStreak?currentStreak : longestStreak;last_num (*it); }return longestStreak;}
}; 思路哈希表 class Solution {
public:int longestConsecutive(vectorint nums) {unordered_setint nums_set; //无序存储基本操作的复杂度大多为常数级for(const int num:nums){nums_set.insert(num);}int longestStreak 0;for(int num : nums_set){if(nums_set.count(num - 1) 0){ //它返回元素在集合中出现的次数。set容器仅包含唯一元素因此只能返回1或0int currentNum num;int currentStreak 1;while(nums_set.count(currentNum 1)){currentNum ;currentStreak ;}longestStreak longestStreak currentStreak ? currentStreak : longestStreak;}}return longestStreak;}
};
