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

数组中的最长连续子序列

http://www.nowcoder.com/practice/eac1c953170243338f941959146ac4bf

先用unordered_set去重,然后遍历哈希set中的元素x,当存在x-1时说明从x开始找得到的长度并不是最大,直接跳过,否则,从x开始,不断寻找x+1,x+2...,记录最大长度。

class Solution {
public:
    /**
     * max increasing subsequence
     * @param arr int整型vector the array
     * @return int整型
     */
    int MLS(vector<int>& arr) {
        unordered_set<int> un_set{};
        for(auto x: arr) un_set.insert(x);
        int max_len{};
        for(auto x: un_set){
            if(!un_set.count(x-1)){
                int cur_x=x;
                int cur_len=1;
                while(un_set.count(cur_x+1)){
                    cur_x++;
                    cur_len++;
                }
                max_len=max(max_len,cur_len);
            }
        }
        return max_len;
    }
};
全部评论

相关推荐

缓解焦虑的最好方法是回家。鼠鼠昨天上午考完了本科阶段的最后一场考试,大概率考得稀烂,但是没多想,考完立马收拾行李,坐上了提前约好的顺风车飞奔回家。虽然家和学校很近,只有一百多公里的路程,但距离上次回家也已经有三四个月了。每次想回家,期间总有考试、毕业设计、面试、实习等等各种各样的原因,没办法回去,待在学校和公司的每一天也都充斥着无形的压力和焦虑。现在终于完成了答辩,考完了试,公司那边也请了假,是时候回去一趟了。没有提前通知爸妈,想给他们一个惊喜。下午提前到了家,他俩还在上班,只好让外公外婆来给我开门。因为我的回家,晚上外婆在厨房格外忙碌,做了满满一大桌子菜,填饱了我天天吃外卖的肚子。晚上也没空...
梦想是成为七海千秋:取决于家庭吧?其实回家更焦虑了,每天起床父母都问实习找好了没简历投递了没今天有没有面试,但是又没有什么结果,玩两下手机父母就会说你看你啥也没找到为什么天天就知道刷手机,怎么不去学习…我现在就希望我能永远在外面实习,报喜不报忧,等拿到一个好offer再回家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务