Longest Consecutive Sequence
用HashMap来空间换时间.
1. 在map中创建一些集合来表示连续的空间。比如，如果有[3，4，5]这样的一个集合，我们表示为key:3， value:5和key:5， value3两个集合，并且把这2个放在hashmap中。这样我们可以在O(1)的时间查询某个数字开头和结尾的集合。
2. 来了一个新的数字时，比如：N=6，我们可以搜索以N-1结尾 以N+1开头的集合有没有存在。从1中可以看到，key:5是存在的，这样我们可以删除3，5和5，3这两个key-value对，同样我们要查以7起头的集合有没有存在，同样可以删除以7起始的集合。删除后我们可以更新left,right的值，也就是合并和扩大集合。
3. 合并以上这些集合，创建一个以新的left,right作为开头，结尾的集合，分别以left, right作为key存储在map中。并且更新max (表示最长连续集合）
1 public class Solution { 2 public int longestConsecutive(int[] num) { 3 if (num == null) { 4 return 0; 5 } 6 7 HashMap map = new HashMap (); 8 9 int max = 0;10 11 int len = num.length;12 for (int i = 0; i < len ; i++) {13 // 寻找以num[i] 起头或是结尾的，如果找到，则可以跳过，因为我们14 // 不需要重复的数字15 if (map.get(num[i]) != null) {16 continue;17 }18 19 int left = num[i];20 int right = num[i];21 22 // 寻找左边界23 Integer board = map.get(num[i] - 1);24 if (board != null && board < left) {25 // 更新左边界26 left = board;27 28 // 删除左边2个集合29 map.remove(left);30 map.remove(num[i] - 1);31 }32 33 // 寻找右边界34 board = map.get(num[i] + 1);35 if (board != null && board > right) {36 // 更新右边界37 right = board;38 39 // 删除右边2个集合40 map.remove(right);41 map.remove(num[i] + 1);42 }43 44 // 创建新的合并之后的集合45 map.put(left, right);46 map.put(right, left);47 48 max = Math.max(max, right - left + 1);49 }50 51 return max;52 }53 }
SOLUTION2:
我们可以把所有的数字放在hashset中，来一个数字后，取出HashSet中的某一元素x，找x-1,x-2....x+1,x+2...是否也在set里。
1 // solution 2: use hashset. 2 public int longestConsecutive(int[] num) { 3 if (num == null) { 4 return 0; 5 } 6 7 HashSet set = new HashSet (); 8 for (int i: num) { 9 set.add(i);10 }11 12 int max = 0;13 for (int i: num) {14 int cnt = 1;15 set.remove(i);16 17 int tmp = i - 1;18 while (set.contains(tmp)) {19 set.remove(tmp);20 cnt++;21 tmp--;22 }23 24 tmp = i + 1;25 while (set.contains(tmp)) {26 set.remove(tmp);27 cnt++;28 tmp++;29 }30 31 max = Math.max(max, cnt);32 }33 34 return max;35 } 2015.1.2 redo:
1 public class Solution { 2 public int longestConsecutive(int[] num) { 3 if (num == null) { 4 return 0; 5 } 6 7 HashSet set = new HashSet (); 8 for (int i: num) { 9 set.add(i);10 }11 12 int max = 0;13 14 for (int i: num) {15 set.remove(i);16 int sum = 1;17 18 int tmp = i - 1;19 while (set.contains(tmp)) {20 // bug 1：forget to add the remove statement.21 set.remove(tmp);22 sum++;23 tmp--;24 }25 26 tmp = i + 1;27 while (set.contains(tmp)) {28 set.remove(tmp);29 sum++;30 tmp++;31 }32 33 max = Math.max(max, sum);34 }35 36 return max;37 }38 }
GITHUB: