C++LeetCode 구현(128.최 장 연속 시퀀스 구하 기)

[LeetCode]128.Longest Consecutive Sequence 최 장 연속 시퀀스 구하 기
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is
[1, 2, 3, 4]
. Therefore its length is 4.
이 문 제 는 최 장 연속 서열 을 요구 하고 O(n)의 복잡 도 제한 을 정 했다.우리 의 생각 은 하나의 집합 HashSet 을 사용 하여 모든 숫자 를 저장 한 다음 에 배열 의 모든 숫자 를 옮 겨 다 니 며 집합 에 존재 한다 면 이 를 제거 한 다음 에 각각 두 개의 변수 pre 와 next 로 앞의 숫자 와 뒤의 수 를 계산 한 다음 에 집합 에서 반복 해서 찾 는 것 이다.pre 가 집합 에 있 으 면 pre 를 집합 에서 제거 한 다음 pre 는 1 을 줄 이 고 pre 가 집합 에 없 을 때 까지 next 에 똑 같은 방법 을 사용 하면 next-pre-1 은 현재 숫자의 최 장 연속 서열 이 며 res 를 업데이트 하면 됩 니 다.집합 에 어떤 숫자 가 존재 하 는 지 확인 할 때 왜 숫자 를 제거 해 야 하 는 지 다시 말 해 보 자.이것 은 대량의 중복 계산 을 피하 기 위해 서 입 니 다.문제 의 예 를 들 어 보 세 요.우 리 는 4 까지 옮 겨 다 닐 때 3,2,1 을 아래로 옮 겨 다 닙 니 다.숫자 를 제거 하지 않 으 면 1 까지 옮 겨 다 닐 때 2,3,4 를 옮 겨 다 닙 니 다.마찬가지 로 3 까지 옮 겨 다 닐 때 4,아래로 2,1 등 을 옮 겨 다 닌 다.만약 에 배열 에 대량의 연속 숫자 가 있다 면 대량의 중복 계산 이 있 고 매우 효율 적 이지 않 기 때문에 우 리 는 HashSet 에서 숫자 를 제거 해 야 한다.코드 는 다음 과 같다.
C++해법 1:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_set<int> s(nums.begin(), nums.end());
        for (int val : nums) {
            if (!s.count(val)) continue;
            s.erase(val);
            int pre = val - 1, next = val + 1;
            while (s.count(pre)) s.erase(pre--);
            while (s.count(next)) s.erase(next++);
            res = max(res, next - pre - 1);
        }
        return res;
    }
};

자바 해법 1:

public class Solution {
    public int longestConsecutive(int[] nums) {
        int res = 0;
        Set<Integer> s = new HashSet<Integer>();
        for (int num : nums) s.add(num);
        for (int num : nums) {
            if (s.remove(num)) {
                int pre = num - 1, next = num + 1;
                while (s.remove(pre)) --pre;
                while (s.remove(next)) ++next;
                res = Math.max(res, next - pre - 1);
            }
        }
        return res;
    }
}

우 리 는 해시 표를 사용 하여 할 수 있 습 니 다.처음에 HashMap 이 비어 있 었 고 모든 숫자 를 옮 겨 다 녔 습 니 다.만약 에 이 숫자 가 HashMap 에 없 으 면 좌우 두 개의 숫자 가 HashMap 에 있 는 지,있 으 면 해시 표 에 있 는 맵 값 을 되 돌려 주 고 없 으 면 0 으로 되 돌려 줍 니 다.비록 우 리 는 HashMap 에서 존재 하지 않 는 맵 값 을 직접 찾 을 수 있 지만 0 을 찾 을 수 있 습 니 다.그러나 가 져 오 면 0 인 맵 이 자동 으로 생 성 됩 니 다.그러면 여기 서 for 순환 의 시작 부분 에서 맵 이 존재 하면 건 너 뛰 면 오류 가 발생 합 니 다.그 다음 에 우 리 는 left+right+1 을 현재 숫자의 맵 으로 하고 res 결 과 를 업데이트 하 며 num-left 와 num-right 의 맵 값 을 업데이트 합 니 다.
맵 이 어떻게 존재 하 는 지 판단 할 때 건 너 뛰 는 이 유 는 어떤 숫자 가 맵 을 만 들 었 을 때 이 숫자 가 이미 처리 되 었 다 는 것 을 설명 하기 때 문 입 니 다.그러면 그 주변의 숫자 도 맵 을 만 들 었 을 가능성 이 높 습 니 다.전에 처 리 된 숫자 를 만 나 인접 한 숫자의 맵 값 을 누적 하면 오류 가 발생 할 수 있 습 니 다.예 를 들 어 배열[1,2,0,1],0 이 실 행 된 후에 HashMap 의 매 핑 은{1->2,2->3,0->3}으로 이때 0 과 2 의 매 핑 값 이 모두 3 임 을 알 수 있 습 니 다.그러면 마지막 1 이 원래 의 방법 으로 처리 한 다음 에 결 과 를 얻 으 면 7 이 고 주제 에 맞지 않 습 니 다.그리고 앞에서 말 한 바 와 같이 존재 하지 않 는 맵 값 에 접근 하지 않도록 자동 으로 맵 을 만 듭 니 다.우 리 는 m.count()를 사용 하여 먼저 검 측 을 합 니 다.맵 이 존재 해 야 우 리 는 그 중에서 값 을 얻 을 수 있 습 니 다.그렇지 않 으 면 직접 값 을 0 으로 할당 합 니 다.코드 는 다음 과 같 습 니 다.
C++해법 2:

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_map<int, int> m;
        for (int num : nums) {
            if (m.count(num)) continue;
            int left = m.count(num - 1) ? m[num - 1] : 0;
            int right = m.count(num + 1) ? m[num + 1] : 0;
            int sum = left + right + 1;
            m[num] = sum;
            res = max(res, sum);
            m[num - left] = sum;
            m[num + right] = sum;
        }
        return res;
    }
};

자바 해법 2:

public class Solution {
    public int longestConsecutive(int[] nums) {
        int res = 0;
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (m.containsKey(num)) continue;
            int left = m.containsKey(num - 1) ? m.get(num - 1) : 0;
            int right = m.containsKey(num + 1) ? m.get(num + 1) : 0;
            int sum = left + right + 1;
            m.put(num, sum);
            res = Math.max(res, sum);
            m.put(num - left, sum);
            m.put(num + right, sum);
        }
        return res;
    }
}

유사 한 제목:
Binary Tree Longest Consecutive Sequence
참고 자료:
https://leetcode.com/problems/longest-consecutive-sequence/
https://leetcode.com/problems/longest-consecutive-sequence/discuss/41055/my-really-simple-java-on-solution-accepted
https://leetcode.com/problems/longest-consecutive-sequence/discuss/41060/a-simple-csolution-using-unordered_setand-simple-consideration-about-this-problem
C++구현 LeetCode(128.최 장 연속 시퀀스)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 최 장 연속 시퀀스 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!