[leetcode]Longest Consecutive Sequence

新博文地址：[leetcode]Longest Consecutive Sequence

Longest Consecutive Sequence

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.

 好吧，这道题我看了别人的提示，具体的思路是，遇到一个数，就将所有左右相邻的数组给剔除掉，并同时计数，例如，找到99的时候，接着找100和98，找100的时候，找101和99（这个刚才找到了，已经剔除了，就不找了），同理找到101时，就找102。宏观来看，就是找到99，就分为两个分支，一支向上搜，一支向下搜：一直找到没有邻接元素为止。

	public int longestConsecutive(int[] num) {
		if (num == null || num.length == 0) {
			return 0;
		}
		Set<Integer> set = new HashSet<Integer>();
		int max = 0;
		for(int tem : num){
			set.add(tem);
		}
		for(int tem : num){
			if(set.contains(tem)){
				int length = findPreOrPost(tem, set);
				max = length > max ? length : max;
			}
		}
		return max;
	}

	private int findPreOrPost(int num, Set<Integer> set) {
		if (set.contains(num)) {
			set.remove(num);
			int preLen = findPreOrPost(num + 1, set) + 1;
			int postLen = findPreOrPost(num - 1, set) + 1;
			return preLen + postLen - 1;
		}
		return 0;
	}