首页 > 其他 > 详细

128. Longest Consecutive Sequence

时间:2018-01-01 16:08:03      阅读:277      评论:0      收藏:0      [点我收藏+]

欢迎fork and star:Nowcoder-Repository-github

128. Longest Consecutive Sequence

题目

 Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity. 

解析

  • I have seen a lot of discussion about this problem.In my opinion,it is not correct to use set(which is ordered),because very time we insert an element to a ordered set,it will cost O(n),so the total complexity is O(nlogn),which violates the request of the problem.So here we use an unordered_set,and one is enough.

  • Besides,to think about this problem,one principle issue we should realize is that usually when we want to reduce the time complexity,we have to increase the space complexity.In this case,if we want to access an element within O(1),we have to use hash table.

  • 另外思考一下hash的迭代器实现方法??


// Longest Consecutive Sequence
class Solution_128 {
public:
    int longestConsecutive(vector<int> &num) {
        if (num.size()==0)
        {
            return 0;
        }

        unordered_set<int> hash(num.begin(), num.end()); //O(n),插入hash表中

        int ret = 1;

        for (auto cur:num) //遍历元素O(n)
        {
            if (hash.find(cur)==hash.end()) //未找到当前元素
            {
                continue;
            }
            hash.erase(cur);

            int pre = cur - 1, next = cur + 1; //下一个连续序列重新赋值
            while (hash.find(pre)!=hash.end()) //hash的迭代器怎么实现?
            {
                hash.erase(pre);
                pre--;
            }
            while (hash.find(next)!=hash.end())
            {
                hash.erase(next);
                next++;
            }

            ret = max(ret, next - pre -  1); // bug : next - pre - 1
        }

        return ret;
    }
};

题目来源

128. Longest Consecutive Sequence

原文:https://www.cnblogs.com/ranjiewen/p/8167078.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!