[leetcode - 128. Longest Consecutive Sequence] java

문제 설명

1. 정렬되지 않은 배열이 주어진다.

2. 숫자가 이어지는(1, 2, 3, 4 ... 이렇게) 길이 중 최대값을 구하면 된다.

3. O(n) 으로만 가능

풀이 과정

1. 참고로 O(n) 이라는게 배수까지는 인정(그니까 제곱이나 로그가 아니라 걍 O(2n) 이런거는 어차피 시간 차이가 적기 때문에 O(n) 으로 통일)

2. 그래서 정렬하고 차이 구하면 굉장히 간단하다.

3. 먼저 배열을 정렬하고

4. 다시 한번 돌면서

5. 이전보다 지금것이 1만큼 크면 이어지는 숫자이고

6. 이전이랑 지금이 같으면 상관 없고(이거는 같은거라 영향 X)
7. 2이상 차이가 나면 끊어짐(초기화)

8. 하면 끝. 간단하다.

코드

class Solution {
    public int longestConsecutive(int[] nums) {
        // 없으면 걍 0
        if(nums.length == 0) return 0;

        int ans = 1;
        int cnt = 1;

        Arrays.sort(nums); // 최초 정렬 진행 -> O(n)
        for(int i=1; i<nums.length; i++) { // n의 갯수에 대해 진행 -> O(n)
            if(nums[i]-1 == nums[i-1]) { // 숫자가 증가한다면 이어진 숫자이다.
                cnt++;
            } else if(nums[i] != nums[i-1]) { // 참고로 같은 숫자가 연이어 있어도 문제가 없다. 그게 아닌 경우만 끊어짐
                cnt = 1;
            }
            ans = Math.max(ans, cnt); // 정렬 진행
        }

        return ans;
    }
}