力扣学习笔记——128.最长连续序列

题目描述

https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-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(vector<int>& nums) {if (0==nums.size()){return 0;}std::sort(nums.begin(),nums.end());// for (auto it=nums.begin();it!=nums.end();it++)// {//     std::cout<<*it<<std::endl;// }int max_result=1;int max_result_temp=1;for(int i=nums.size()-1;i>0;--i){// std::cout<<"i="<<i<<std::endl;// std::cout<<"nums[i]="<<nums[i]<<std::endl;// std::cout<<"nums[i-1]="<<nums[i-1]<<std::endl;if(1==(nums[i]-nums[i-1])){max_result_temp++;//std::cout<<"max_result_temp="<<max_result_temp<<std::endl;if (max_result_temp>max_result){max_result=max_result_temp;}}else if(0==(nums[i]-nums[i-1])){max_result_temp;//std::cout<<"max_result_temp="<<max_result_temp<<std::endl;if (max_result_temp>max_result){max_result=max_result_temp;}}else{// is_consecutive=false;max_result_temp=1;}}return max_result;}
};

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <string>class Solution
{
public:int longestConsecutive(std::vector<int> &nums){if (0 == nums.size()){return 0;}std::sort(nums.begin(), nums.end());// for (auto it=nums.begin();it!=nums.end();it++)// {//     std::cout<<*it<<std::endl;// }int max_result = 1;int max_result_temp = 1;for (int i = nums.size() - 1; i > 0; --i){// std::cout<<"i="<<i<<std::endl;// std::cout<<"nums[i]="<<nums[i]<<std::endl;// std::cout<<"nums[i-1]="<<nums[i-1]<<std::endl;if (1 == (nums[i] - nums[i - 1])){max_result_temp++;// std::cout<<"max_result_temp="<<max_result_temp<<std::endl;if (max_result_temp > max_result){max_result = max_result_temp;}}else if (0 == (nums[i] - nums[i - 1])){max_result_temp;// std::cout<<"max_result_temp="<<max_result_temp<<std::endl;if (max_result_temp > max_result){max_result = max_result_temp;}}else{// is_consecutive=false;max_result_temp = 1;}}return max_result;}
};int main()
{std::vector<int> 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 <vector>int main() {std::vector<int> 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;}

其他优化解题

使用哈希表