My code:
public class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
HashSet<Integer> helper = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++)
helper.add(nums[i]);
int len = 1;
int longestLen = 1;
for (int i = 0; i < nums.length; i++) {
int tmp = nums[i];
if (!helper.contains(tmp))
continue;
while (helper.contains(tmp - 1)) {
helper.remove(tmp - 1);
len++;
tmp--;
}
tmp = nums[i];
while (helper.contains(tmp + 1)) {
helper.remove(tmp + 1);
len++;
tmp++;
}
helper.remove(nums[i]);
longestLen = Math.max(longestLen, len);
len = 1;
}
return longestLen;
}
}
看了提示思路之后才寫出來(lái)。好奇怪魁衙，為什么自己想就想不出來(lái)报腔！
就是一個(gè)左右不斷合并的過(guò)程。然后不斷把已經(jīng)探明過(guò)的值從HashSet中刪除以避免重復(fù)探測(cè)剖淀。
參考網(wǎng)址：
http://www.programcreek.com/2013/01/leetcode-longest-consecutive-sequence-java/
然后還有一種 Union Find 的做法纯蛾。
我看了網(wǎng)上對(duì)該算法的解釋和Discuss里面的代碼后自己重寫了一個(gè)，
public class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
Union union = new Union(nums.length);
HashMap<Integer, Integer> helper = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (helper.containsKey(nums[i])) {
continue;
}
helper.put(nums[i], i);
if (helper.containsKey(nums[i] - 1))
union.union(i, helper.get(nums[i] - 1));
if (helper.containsKey(nums[i] + 1))
union.union(i, helper.get(nums[i] + 1));
}
return union.maxUnion();
}
private class Union {
int[] unions;
int[] size;
int count;
Union(int n) {
unions = new int[n];
size = new int[n];
count = n;
for (int i = 0; i < n; i++) {
unions[i] = i;
size[i] = 1;
}
}
/** return the group id of this index */
int find(int p) {
if (p >= unions.length)
return -1;
while (p != unions[p])
p = unions[p];
return p;
}
/** test whether two indexs are connectted */
boolean connected(int p, int q) {
p = find(p);
q = find(q);
return p == q;
}
/** connect two components by making their group id equal */
void union(int p, int q) {
p = find(p);
q = find(q);
if (size[p] > size[q]) {
size[p] += size[q];
unions[q] = p;
}
else {
size[q] += size[p];
unions[p] = q;
}
count--;
}
/** return the maximum size of components */
int maxUnion() {
int max = 1;
for (int i = 0; i < unions.length; i++) {
max = Math.max(max, size[i]);
}
return max;
}
}
}
然后是Discuss里面的代碼：
https://leetcode.com/discuss/68905/my-java-solution-using-unionfound
我比他更快的原因在于纵隔，我提前做了一個(gè)size數(shù)組專門用來(lái)記錄大小翻诉，并且當(dāng)合并樹的時(shí)候可以使該算法更快。
Union Find 是普林斯頓算法第一章講的東西捌刮，當(dāng)時(shí)理解起來(lái)還有些困難∨龌停現(xiàn)在思考下，覺得這個(gè)算法的確不錯(cuò)糊啡。它解決了什么問題拄查？
當(dāng)我們需要根據(jù)value將index連接起來(lái)吁津，而index又相鄰時(shí)棚蓄，
Union Find 用代碼解決了這個(gè) ** 連接結(jié)點(diǎn) ** 的問題堕扶。
Nice Algorithm!
一個(gè)比較全面的算法講解：
http://blog.csdn.net/dm_vincent/article/details/7655764
Anyway, Good luck, Richardo!
