[LeetCode] 128. Longest Consecutive Sequence (python,C++)

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

Longest Consecutive Sequence - LeetCode

'You must write an algorithm that runs in O(n) time.' 에 주의하자. 해당 문제를 정렬후에 푼다면 O(NlogN)이 걸린다. 더욱 빨리 푸는방법이 있을까...? 집합을 이용해보자. 먼저,주어진 리스트를 set에 담고,시작점을 파악한다.

이전 숫자가 없다면 시작지점이다.

그 후 시작지점 부터 1씩 더한값이 set에 존재하는지 확인하고,있다면 길이+1을 해준다.

여기서 새로 알게된점.

 

• List에서 in 연산은 O(n)으로 선형시간으로 탐색. 반면에 set이나 dict는 O(1)로 상수시간으로 탐색
• 따라서 많은 양의 데이터에서 in으로 값을 검색하고자 할 때는 set으로 변환하면 더 빠름

---

SOLUTION CODE

# PYTHON

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet=set(nums)
        longest=0

        for n in nums:
            # check if its the start of a sequence
            # 시작점 체크
            if (n - 1) not in numSet:
                length = 0
                # 현재val부터 +1하면서 set에존재하는지 check
                while(n+length) in numSet:
                    length+=1
                longest=max(length,longest)
        return longest

 

# C++

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet;
        int longest=0;

        // list->set
        for(int i:nums) numSet.insert(i);

        for(int i=0;i<nums.size();i++){
            // 시작점인지 체크
            if(numSet.find(nums[i]-1)==numSet.end()){
                // 시작점이면,다음 원소 체크
                int length=0;
                while(numSet.find(nums[i]+length)!=numSet.end()) length+=1;
                longest = max(longest,length);
            }
        }
        return longest;
    }
};

---

 //존재 하는 원소 찾기
iter = s.find(30);
if(iter != s.end()){
    cout << *iter << " : 존재 " << endl; 
}else{
    cout << "존재하지 않음 " << endl; 
}