对于每一个n，检查是否为一个consecutive sequence的下边界，也就是n-1不存在于set中，再逐次检查n + 1, n + 2, n + 3...是否在set中，最终得到另一个上边界（+1）m，所以sequence的长度为m - n （也可以是n+1不存在于set中，则反向检查）。转为set，时间O(n)，之后对于set中的每一个元素，如果是一个连续序列的下边界，则对这个连续序列进行，因为对于每一个连续序列实际只会扫描一遍，所以这个循环最终是O(n)时间复杂度的。
Whenever a new element n is inserted into the map, do two things:
See if n - 1 and n + 1 exist in the map, and if so, it means there is an existing sequence next to n. Variables left and right will be the length of those two sequences, while 0 means there is no sequence and n will be the boundary point later. Store (left + right + 1) as the associated value to key n into the map.
Use left and right to locate the other end of the sequences to the left and right of n respectively, and replace the value with the new length.
Everything inside the for loop is O(1) so the total time is O(n)
Solution
O(n) HashMap - store sequence length in the boundary points of the sequence
The key thing is to keep track of the sequence length and store that in the boundary points of the sequence. For example, as a result, for sequence {1, 2, 3, 4, 5}, map.get(1) and map.get(5) should both return 5.
public int longestConsecutive(int[] num) {
int res = 0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int n : num) {
if (!map.containsKey(n)) {
int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
// sum: length of the sequence n is in
int sum = left + right + 1;
map.put(n, sum);
// keep track of the max length
res = Math.max(res, sum);
// extend the length to the boundary(s)
// of the sequence
// will do nothing if n has no neighbors
map.put(n - left, sum);
map.put(n + right, sum);
}
else {
// duplicates
continue;
}
}
return res;
}
Another implementation
public int longestConsecutive(int[] nums) {
Map<Integer,Integer> ranges = new HashMap<>();
int max = 0;
for (int num : nums) {
if (ranges.containsKey(num)) continue;
// 1.Find left and right num
int left = ranges.getOrDefault(num - 1, 0);
int right = ranges.getOrDefault(num + 1, 0);
int sum = left + right + 1;
max = Math.max(max, sum);
// 2.Union by only updating boundary
// Leave middle k-v dirty to avoid cascading update
if (left > 0) ranges.put(num - left, sum);
if (right > 0) ranges.put(num + right, sum);
ranges.put(num, sum); // Keep each number in Map to de-duplicate
}
return max;
}
*O(n) TIme: Convert to set, loop lower bound consecutive sequence
(10ms - 51.32% AC) HashSet and Intelligent Sequence Building
We only attempt to build sequences from numbers that are not already part of a longer sequence. This is accomplished by first ensuring that the number that would immediately precede the current number in a sequence is not present, as that number would necessarily be part of a longer sequence.
public class Solution {
/**
* @param nums: A list of integers
* @return an integer
*/
public int longestConsecutive(int[] nums) {
// write you code here
Set<Integer> hs = new HashSet<Integer>();
for (int n : nums) {
hs.add(n);
}
int longest = 0;
for (int n : hs) {
if (!hs.contains(n - 1)) {
int m = n + 1;
while (hs.contains(m)) {
m++;
}
longest = Math.max(longest, m - n);
}
}
return longest;
}
}
*HashSet - (7ms 86.82% AC) LeetCode Official Solution
HashSet and Intelligent Sequence Building
class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) return 0;
Set<Integer> numSet = new HashSet<Integer>();
for (int num: nums) {
numSet.add(num);
}
int longestStreak = 1;
for (int num: numSet) {
int currentStreak = 1;
int currentNum = num;
if (!numSet.contains(num - 1)) {
while (numSet.contains(currentNum + 1)) {
currentStreak++;
currentNum++;
}
longestStreak = Math.max (currentStreak, longestStreak);
}
}
return longestStreak;
}
}
HashSet - Convert to set, expand left, right index and remove from set
public int longestConsecutive(int[] nums) {
if(nums == null || nums.length == 0) return 0;
Set<Integer> set = new HashSet<>();
for(int i : nums) set.add(i);
int ans = 0;
for(int num : nums) {
int left = num - 1;
int right = num + 1;
while(set.remove(left)) left--;
while(set.remove(right)) right++;
ans = Math.max(ans,right - left - 1);
if(set.isEmpty()) return ans;//save time if there are items in nums, but no item in hashset.
}
return ans;
}
Sorting First - (4ms 94.51% AC)
Time complexity : O(nlgn). The main for loop does constant work nn times, so the algorithm's time complexity is dominated by the invocation of sort, which will run in O(nlgn) time for any sensible implementation.
Space complexity : O(1) (or O(n)). Depending on whether we can modify the input array with sorting the input array in place. If not, we must spend linear space to store a sorted copy.
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int longestStreak = 1;
int currentStreak = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i-1]) {
if (nums[i] == nums[i-1]+1) {
currentStreak += 1;
}
else {
longestStreak = Math.max(longestStreak, currentStreak);
currentStreak = 1;
}
}
}
return Math.max(longestStreak, currentStreak);
}
}
Union Find - (9ms 64.18% AC)
public class Solution {
public int longestConsecutive(int[] nums) {
UF uf = new UF(nums.length);
Map<Integer,Integer> map = new HashMap<Integer,Integer>(); // <value,index>
for(int i=0; i<nums.length; i++){
if(map.containsKey(nums[i])){
continue;
}
map.put(nums[i],i);
if(map.containsKey(nums[i]+1)){
uf.union(i,map.get(nums[i]+1));
}
if(map.containsKey(nums[i]-1)){
uf.union(i,map.get(nums[i]-1));
}
}
return uf.maxUnion();
}
}
class UF{
private int[] list;
public UF(int n){
list = new int[n];
for(int i=0; i<n; i++){
list[i] = i;
}
}
private int root(int i){
while(i!=list[i]){
list[i] = list[list[i]];
i = list[i];
}
return i;
}
public boolean connected(int i, int j){
return root(i) == root(j);
}
public void union(int p, int q){
int i = root(p);
int j = root(q);
list[i] = j;
}
// returns the maxium size of union
public int maxUnion(){ // O(n)
int[] count = new int[list.length];
int max = 0;
for(int i=0; i<list.length; i++){
count[root(i)] ++;
max = Math.max(max, count[root(i)]);
}
return max;
}
}
对于第一种思路，具体的解释如下：
第二种思路来源：
HashSet O(n) solution runtime 5 ms, faster than 91.70% via