[leetcode 128] Longest Consecutive Sequence

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

Follow up: Could you implement the O(n) solution? 

 

Example 1:

Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9

 

Constraints:

• 0 <= nums.length <= 104
• -109 <= nums[i] <= 109

문제 풀이

난이도 hard치곤 쉬운거 같다.

 

첫번째 방법: sort 사용

중복 값도 존재하므로 현재 값과 이전 값이 다를때 1차이가 나는지 확인한다. 1차이가 난다면 길이+1 그렇지 않다면 길이=1로 초기화한다.

 

class Solution {
    public int longestConsecutive(int[] nums) {
        
        if(nums.length == 0){
            return 0;
        }
        
        Arrays.sort(nums);
        
        int tmp = 1, result = 1;
        
        for(int i=1; i<nums.length; i++){
            if(nums[i]!= nums[i-1]){
                if(nums[i-1] + 1 == nums[i]){
                    tmp++;
                }else {
                    result = Math.max(result, tmp);
                    tmp = 1;
                }
            }
        }
        
        return Math.max(result, tmp);
    }
}

 

두 번째 방법: set사용

set에 담아서 중복값을 없앤다. 현재 값보다 -1인 값이 있는지 체크하여 이미 최대길이에 반영한 원소인지 확인한다.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int len = nums.size();
        if(len == 0){
            return 0;
        }
        
        set<int> s;
        
        for(int i=0; i<len; i++){
            s.insert(nums[i]);
        }
        
        int result = 0;
        for(int num: nums){
            if(s.find(num-1) == s.end()){
                int cur = num;
                int tmpLen = 1;
                
                while(s.find(cur+1) != s.end()){
                    tmpLen++;
                    cur++;
                }
                
                result = max(result, tmpLen);
            }
        }
        
        return result;
    }
};