leetcode_longest_consecutive_sequence

发表于

难度：Hard

题目要求：
O(n)时间。
解题思路：
第一种思路，先找出最大值max、最小值min，然后申请大小max-min+1的hash数组，将原始数组映射过来。遍历一遍hash数组，找最长的。这种方法遇到[-88888888,0,88888888]会tle。
第二种思路，用set，将数组存到set里面。然后遍历数组，以每个元素为初始值，找最长的。这种方法遇到[0,1,2…….,10000]的时候会RunTimeError。
怎么办？直接sort了一下数组，然后找最长的连续值。竟然过了。。不过题目要求是O(n)的时间，sort这里会不会算是作弊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int longest = 0, length = 0;
        for(auto it = nums.begin(); it != nums.end(); it++)
        {
            if(it == nums.begin())
            {
                length=1;
                longest=1;
            }
            else
            {
                if(*it == *(it-1)+1)
                {
                    length++;
                    longest = longest > length ? longest :length;
                    // longest = max(length,longest);
                }
                else if(*it == *(it-1))
                {
                    continue;
                }
                else
                {
                    length=1;
                }
            }
        }
        return longest;
    }
};

运行结果：16ms，超过92.63%

分割线

看了答案，调用sort是作弊行为。
按照上面set的思路继续分析。将数组存到set里面。然后遍历数组，寻找当前元素所在区间的最大最小值，同时删除掉该区间的值，找出最大的区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int longest = 1;
        // for(int i = 0; i < nums.size(); i++)
        //     s.insert(nums[i]);
        for(int i = 0; i < nums.size(); i++)
        {
            int cur_val = nums[i];
            if(s.find(cur_val) != s.end())
            {
                int count = 1;
                s.erase(cur_val);
                int up = cur_val+1;
                while(s.find(up) != s.end())
                {
                    s.erase(up);
                    count++;
                    up++;
                }
                int down = cur_val-1;
                while(s.find(down) != s.end())
                {
                    s.erase(down);
                    count++;
                    down--;
                }
                longest = max(longest,count);
            }
        }
        return longest;
    }
};

运行时间：19ms，超过73.61%。(使用set的运行时间为39ms)