网站招标书怎么做,哪个网站做期货数字币,仿知乎 wordpress,吉林网站建设哪家好题目描述
https://leetcode.cn/problems/longest-consecutive-sequence/description/?envTypestudy-plan-v2envIdtop-100-liked
给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。
请你…题目描述
https://leetcode.cn/problems/longest-consecutive-sequence/description/?envTypestudy-plan-v2envIdtop-100-liked
给定一个未排序的整数数组 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
我的答案
class Solution {
public:int longestConsecutive(vectorint nums) {if (0nums.size()){return 0;}std::sort(nums.begin(),nums.end());// for (auto itnums.begin();it!nums.end();it)// {// std::cout*itstd::endl;// }int max_result1;int max_result_temp1;for(int inums.size()-1;i0;--i){// std::coutiistd::endl;// std::coutnums[i]nums[i]std::endl;// std::coutnums[i-1]nums[i-1]std::endl;if(1(nums[i]-nums[i-1])){max_result_temp;//std::coutmax_result_tempmax_result_tempstd::endl;if (max_result_tempmax_result){max_resultmax_result_temp;}}else if(0(nums[i]-nums[i-1])){max_result_temp;//std::coutmax_result_tempmax_result_tempstd::endl;if (max_result_tempmax_result){max_resultmax_result_temp;}}else{// is_consecutivefalse;max_result_temp1;}}return max_result;}
};#include iostream
#include vector
#include algorithm
#include iostream
#include unordered_map
#include stringclass Solution
{
public:int longestConsecutive(std::vectorint nums){if (0 nums.size()){return 0;}std::sort(nums.begin(), nums.end());// for (auto itnums.begin();it!nums.end();it)// {// std::cout*itstd::endl;// }int max_result 1;int max_result_temp 1;for (int i nums.size() - 1; i 0; --i){// std::coutiistd::endl;// std::coutnums[i]nums[i]std::endl;// std::coutnums[i-1]nums[i-1]std::endl;if (1 (nums[i] - nums[i - 1])){max_result_temp;// std::coutmax_result_tempmax_result_tempstd::endl;if (max_result_temp max_result){max_result max_result_temp;}}else if (0 (nums[i] - nums[i - 1])){max_result_temp;// std::coutmax_result_tempmax_result_tempstd::endl;if (max_result_temp max_result){max_result max_result_temp;}}else{// is_consecutivefalse;max_result_temp 1;}}return max_result;}
};int main()
{std::vectorint nums {100, 4, 200, 1, 3, 2};int result;Solution test1;result test1.longestConsecutive(nums);std::cout result result std::endl;std::cout std::endl;return 0;
}
编译
g 128_最长连续序列.cpp -o main输出
4解题思路
先排序然后倒着循环作差值为1则累加不然重新开始累加记住要记住最大值且需要考虑多种边界情况比如一个数据没有数据重复数据等。特别是重复数据。
注意 后面我会学习排序后去重的C库函数
知识点
sort库函数使用
这里需要包含头文件
#include algorithm不然找不到头文件 在 C 中你可以使用 头文件中的库函数来进行排序。以下是一些常用的排序函数
std::sort()对容器或指定范围内的元素进行排序默认按升序排序。注意std::sort(),不光能对数字进行排序还可以对字母进行排序。
#include algorithm
#include vectorint main() {std::vectorint nums {5, 2, 8, 1, 9};std::sort(nums.begin(), nums.end());// 输出排序后的结果for (const auto num : nums) {std::cout num ;}return 0;
}输出结果1 2 5 8 9
注意输入为0判断边界条件判断
输入数组长度为0 if (0 nums.size()){return 0;}其他优化解题
使用哈希表
