最长连续序列

野性酷女 2023-02-19 12:28 5阅读 0赞

## 一、前言 ##

问题来源LeetCode 128，难度：困难

问题链接：[https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/][https_leetcode-cn.com_problems_longest-continuous-increasing-subsequence]

## 二、题目 ##

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

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

**示例:**

输入: [100, 4, 200, 1, 3, 2]
    输出: 4
    解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

## 三、思路 ##

### 3.1 思路 ###

对无序数组中的数据处理一遍，最快都需要执行n次，时间复杂度是O(n)，也就是我们后续执行需要是线性的。能满足这个要求的也就只有哈希了，和计数排序的思想有点像。通过哈希我们可以判断一个数是否在数组中。

### 3.2 实现过程 ###

C++中unordered\_set底层是用哈希表，我们可以直接用unordered\_set来存储数组，这样我们可以通过判断一个数是否在数组中时间复杂度是O(1)。

**流程：**

1.  将数组中数据添加到unordered\_set中
2.  从头遍历unordered\_set中的元素，当前元素记为 n
3.  如果n-1不在数组中，判断n+1，n+2...，直到不在数组中为止，我们可以求出以元素n为起点的最长连续序列
4.  如果n-1，在数组中，说明n不是最小起点跳过继续循环的一下元素判断。

### 3.3 时间复杂度证明 ###

总共计算次数，将数组中元素记录在unordered\_set中，计算次数是n（可能大于n，但次数是线性增长，粗略处理当着n次），找最长连续序列，循环里面累加搜索次数最大次数是n-1，总次数是3n-1，时间复杂度为O(n)。

## 四、编码实现 ##

//==========================================================================
    /**
    * @file    : 06_LongestConsecutive.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/106875604
    * @author  : niebingyu
    * @title   : 最长连续递增序列
    * @purpose : 给定一个未排序的整数数组，找出最长连续序列的长度。
    * 要求算法的时间复杂度为 O(n)。
    
    * 示例:
    * 输入: [100, 4, 200, 1, 3, 2]
    * 输出: 4
    * 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
    *
    * 来源：力扣（LeetCode）128 困难
    * 链接：https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
    */
    //==========================================================================
    #pragma once
    #include <vector>
    #include <unordered_set>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_LONGESTCONSECUTIVE namespace NAME_LONGESTCONSECUTIVE {
    #define NAMESPACE_LONGESTCONSECUTIVEEND }
    NAMESPACE_LONGESTCONSECUTIVE
    
    class Solution 
    {
    public:
        int longestConsecutive(vector<int>& nums) 
        {
            unordered_set<int> num_set;
            for (const int& num : nums) num_set.insert(num);
    
            int ls = 0;
            for (const int& i : num_set)
            {
                if (!num_set.count(i - 1)) 
                {
                    int ci = i, cs = 1;
                    while (num_set.count(++ci)) cs += 1;
    
                    ls = max(ls, cs);
                }
            }
    
            return ls;
        }
    };
    
    //
    // 测试 用例 START
    void test(const char* testName, vector<int>& nums, int expect)
    {
    	Solution S;
    	int result = S.longestConsecutive(nums);
    
    	// 粗略校验
    	if (result == expect)
    		cout << testName << ", solution passed." << endl;
    	else
    		cout << testName << ", solution failed. result:" << result << " ,expect:" << expect << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<int> nums =
        {
            100, 4, 200, 1, 3, 2
        };
    
        int expect = 4;
    
        test("Test1()", nums, expect);
    }
    
    NAMESPACE_LONGESTCONSECUTIVEEND
    // 测试 用例 END
    //
    
    void LongestConsecutive_Test()
    {
        NAME_LONGESTCONSECUTIVE::Test1();
    }

**执行结果：**

![2020062017594936.png][]

[https_leetcode-cn.com_problems_longest-continuous-increasing-subsequence]: https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
[2020062017594936.png]: https://img-blog.csdnimg.cn/2020062017594936.png