Longest Consecutive Sequence 數組連續數字的情況

Longest Consecutive Sequence 數組連續數字的情況

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.

尋找最大的連續數組的長度，利用兩個set數組，一個數組存儲已經被訪問過的數組，如果已經被訪問過了，那麼就不需要再被訪問了

class Solution {
public:
    int longestConsecutive(vector& nums) {
        if(nums.empty())
        {
            return 0;
        }
        unordered_set existSet;
        unordered_set visitedSet;
        int maxLength = 0;
        for(int i = 0; i < nums.size(); i++)
            existSet.insert(nums[i]);
        for(int i = 0; i < nums.size(); i++)
        {
            int length = 0;
            if(visitedSet.count(nums[i]))
            {
                continue;
            }
            else
            {
                visitedSet.insert(nums[i]);
                length++;
                int left = nums[i];
                int right = nums[i];
                while(existSet.count(--left))
                {
                    visitedSet.insert(left);
                    length++;
                }
                while(existSet.count(++right))//<必須使用?前＋＋
                {
                    visitedSet.insert(right);
                    length++;
                }
                maxLength = max(maxLength,length);
            }
        }
        return maxLength;
    }
};

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

連續數組求最小的miss的數據，還是利用前面介紹的方法，還是利用兩個不同的set，其中一個表示已經訪問過了的情況，只觀察比當前大的數據，

如果已經訪問過了就不訪問了

class Solution {
public:
    int firstMissingPositive(vector& nums) {
        if(nums.empty())
        {
            return 1;
        }
        int missVal = INT_MAX;
        int minVal = 1;
        unordered_set numSet;
        unordered_set visitedSet;
        for_each(nums.begin(),nums.end(),[&numSet](int x)
        {
            if(x >= 0)
                numSet.insert(x);
        });
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] < 0 || visitedSet.count(nums[i]))
            {
                continue;
            }
            int right = nums[i];
            while(numSet.count(++right))
            {
                visitedSet.insert(right);
            }
            missVal = min(missVal,right);
        }
        if(numSet.count(1))
            return missVal;
        else
        {
            return 1;
        }
    }
};