美文网首页LeetCode
Longest Consecutive Sequence解题报告

Longest Consecutive Sequence解题报告

作者: 黑山老水 | 来源:发表于2018-03-25 12:28 被阅读4次

    Description:

    Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
    Your algorithm should run in O(n) complexity.

    Example:

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

    Link:

    https://leetcode.com/problems/longest-consecutive-sequence/description/

    解题方法:

    这道题要求在O(n)时间解出,所以不能对数组进行排序。
    解题思路参考:https://blog.csdn.net/fightforyourdream/article/details/15024861
    O(n)解法为:把所有数都存到hashset中去,每遇到一个数,就把比它大的和比它小的连续的数都找一遍,在找的过程中把这些数都从hashset中删掉,防止重复查找。
    比如例子:100, 4, 200, 1, 3, 2都加入hashset
    当找100时,把100删掉,此时hashset: 4, 200, 1, 3, 2
    .
    .
    .
    当找到4时,找完以后的hashset: 200 (100在第一轮被删掉,1 2 3都在找比4小的连续数过程中都被删掉)

    Time Complexity:

    O(N)

    完整代码:

    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hash;
        for(int i: nums)
            hash.insert(i);
        int result = 0;
        for(int i: nums) {
            int cnt = 1;
            hash.erase(i);
            int temp = i - 1;
            //find less
            while(hash.find(temp) != hash.end()) {
                cnt++;
                hash.erase(temp--);
            }
            temp = i + 1;
            while(hash.find(temp) != hash.end()) {
                cnt++;
                hash.erase(temp++);
            }
            result = max(result, cnt);
        }
        return result;
    }
    

    相关文章

      网友评论

        本文标题:Longest Consecutive Sequence解题报告

        本文链接:https://www.haomeiwen.com/subject/dhphcftx.html