Longest Consecutive Sequence

题目:

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

分析:

hash的元素使用过一次就可以remove掉了,没有什么影响

解法:

public class Solution {
    /**
     * @param nums: A list of integers
     * @return an integer
     */
    public int longestConsecutive(int[] num) {
        // write you code here
        HashSet<Integer> hash = new HashSet<Integer>();
        for (int i = 0; i < num.length; i++) {
            hash.add(num[i]);
        }

        int globalLongest = 1;
        for (int i = 0; i < num.length; i++) {
            int down = num[i] - 1;
            int currLongest = 1;
            while (hash.contains(down) ) {
                hash.remove(down);
                down--;
                currLongest++;
            }
            int up = num[i] + 1;
            while (hash.contains(up) ) {
                hash.remove(up);
                up++;
                currLongest++;
            }
            globalLongest = Math.max(globalLongest, up - down - 1);
        }
        return globalLongest;
    }
}

results matching ""

    No results matching ""