转载

[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.

排序法

复杂度

时间 O(NlogN) 空间 O(1)

思路

将数组排序后，从前向后遍历，找到最长的连续部分，该方法随不符合题意，但是不用空间。

集合法

复杂度

时间 O(N) 空间 O(N)

思路

将所有数都加入集合中，然后再遍历这些数，因为我们能O(1)的判断某个数是否在集合中，所以我们可以一个个向上或者向下检查。为了避免之后重复检查，我们每查到一个数，都要将其从集合中移除。这样每遇到一个数，都检查它的上下边界，就能找出最长的连续数列。时间复杂度仍是O(N)，因为我们不会检查不存在于数组的数，而存在于数组的数也只会检查一次。

代码

public class Solution {  public int longestConsecutive(int[] nums) {   int maxlen = 0;   Set<Integer> set = new HashSet<Integer>();   // 先将所有数字加入数组中   for(int n : nums){    set.add(n);   }   // 对于每个数我们都在集合中一一检查它的上下边界   for(int n : nums){    // 暂存n，供检查下边界时使用    int curr = n, len = 0;    // 一个一个检查上边界    while(set.contains(curr)){     curr++;     len++;     set.remove(curr);    }    // 一个一个检查下边界    curr = n - 1;    while(set.contains(curr)){     curr--;     len++;     set.remove(curr);    }    maxlen = Math.max(len, maxlen);   }   return maxlen;  } }

正文到此结束