题解 | #数组中的最长连续子序列#

数组中的最长连续子序列
题意
给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）

输出描述:
输出数组中最大的连续子序列长度

示例
输入：[100,4,200,1,3,2]
返回值：4

方法一 排序,模拟

由题意可知要求的连续值位置并不影响先后顺序,所以先对原数组进行排序,之后遍历一遍取前后差值为1的最长序列,其中要忽略前后值相同的情况。

int MLS(vector<int>& arr) {
        // write code here
        sort(arr.begin(), arr.end());    //排序序列
        int ans = 1, q = 1,len = arr.size();;
        for(int i = 1; i < len; i ++){    //遍历序列
            if(arr[i] == arr[i - 1]) continue; //如果当前值与前一个值相等则不做操作
            if(arr[i] - arr[i - 1] == 1){    //当前值与前一个值相差1说明值连续
               if(ans < ++q) ans = q;    //更新答案
            }else q = 1;
        }
        return ans;
    }

时间复杂度: 排序与遍历总体复杂度为
空间复杂度: 只使用若干个变量

方法二 STL(set)

set类可以去除重复元素以及使容器内的元素有序，根据第一种方法的思想将set中的容器按次序取出判断即可。

int MLS(vector<int>& arr) {
        // write code here
        set<int> st;
        for(auto x: arr) st.insert(x);    //将序列所有元素插入set中
        int ans = 1, q = 1, pre = *st.begin();
        st.erase(pre); 
        while(st.size()){ //遍历set中所有元素
            int now = *st.begin();
            st.erase(now);
            if(now - pre == 1 ) { //如果set前后相差为1说明两个数连续
                if(ans < ++ q) ans = q;    //更新答案
            }else q = 1; 
            pre = now;
        }
        return ans;
    }

时间复杂度: set插入和删除复杂度都为
空间复杂度: set集合中所有的元素