Leetcode.128.Longest Consecutive

题目

给定一个无序的整型数组, 求数组中连续数的最大长度.

Input: [100,4,200,1,3,2]
Output: 4

思路1

排序, 然后遍历.
时间复杂度O(NlogN)

int longestConsecutive(vector<int>& nums) {
    if (nums.empty()) return 0;
    sort(nums.begin(), nums.end());

    int res = 1;
    int count = 1;
    for(int i = 1; i < nums.size();i++) {
        if (nums[i] == nums[i-1]) {
            continue;
        } else if (nums[i] == nums[i-1]+1) {
            count++;
            if (count > res) {
                res = count;
            }
        } else {
            count = 1;
        }
    }
    return res;
}

思路2

利用set, set会利用红黑树自动排序, 并且会过滤重复数字.
时间复杂度O(n)

int longestConsecutive(vector<int>& nums) {
    if (nums.empty()) return 0;
    set<int> s(nums.begin(), nums.end());
    
    int res = 1;
    int count = 1;
    set<int>::iterator first = s.begin();
    set<int>::iterator last = first++;
    while (last != s.end()) {
        if (*first+1 == *last) {
            count++;
            if (count > res) {
                res = count;
            }
        } else {
            count = 1;
        }
        first = last;
        last++;
    }

    return res;
}

总结

熟悉Set和List工作原理.
学习红黑树.