Leetcode128——Longest Consecutive Sequence

作者:Tyan博客:noahsnail.com  |  CSDN  | 

1.問題の説明

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.
Your algorithm should run in O(n) complexity.

2.解を求める

問題では時間の複雑さがO(n)であることが明確に要求されているので,この問題ではループループループは使用できないに違いない.この問題は主にハッシュテーブルを考察することであり,ハッシュテーブルのクエリ毎の時間複雑度はO(1)であるからである.そこでまず配列をMapに変換します.次に、各数値の前の数と後の数をそれぞれクエリーし、数値の連続数を統計します.ハッシュ・テーブルに隣接する数がある場合は、クエリー後にハッシュ・テーブルから削除する必要があります.もちろん削除しなくてもいいです.ハッシュ・テーブルが空の場合、ループから直接飛び出し、ループしません.

public class Solution {
    public int longestConsecutive(int[] nums) {
        int max = 0;
        int count = 0;
        Map map = new HashMap();
        for(int i = 0; i < nums.length; i++) {
            map.put(String.valueOf(nums[i]), nums[i]);
        }
        for(int i = 0; i < nums.length; i++) {
            count = 1;
            int x = nums[i];
            while(true) {
                int temp = --x;
                if(map.containsKey(String.valueOf(temp))) {
                    map.remove(String.valueOf(temp));
                    count++;
                }else {
                    break;
                }
            }
            // x
            x = nums[i];
            while(true) {
                int temp = ++x;
                if(map.containsKey(String.valueOf(temp))) {
                    map.remove(String.valueOf(temp));
                    count++;
                }else {
                    break;
                }
            }
            if(count > max) {
                max = count;
            }
            if(map.isEmpty()) {
                break;
            }
        }
        return max;
    }
}