title
problem link Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
Follow up:Could you implement the O(n) solution?
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints:
0 4
-109 9
给定一个未排序的整数数组，找出最长连续序列的长度。
solution
uf 不太适合
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
nums = list(set(nums))
uf = {}
def find(x):
uf.setdefault(x, x)
if uf[x] != x:
uf[x] = find(uf[x])
return uf[x]
def union(a, b):
uf[find(a)] = find(b)
numIndex = {nums[i]: i for i in range(len(nums))}
for i, n in enumerate(nums):
uf.setdefault(i, i)
if n + 1 in numIndex:
union(i, numIndex[n + 1])
if n - 1 in numIndex:
union(i, numIndex[n - 1])
rootCount = {}
maxCount = 0
for i in uf:
r = find(i)
rootCount[r] = rootCount.get(r, 0) +1
maxCount = max(maxCount, rootCount[r])
return maxCount
这是一个计数题，别的解法都把它弄复杂了。假设你已经掌握了dict和set，往下看：
拿那个100, 4, 200, 1, 3, 2样例，你该怎么数数呢？你先从100数，然后呢，就没有了。再从4开始数，唉，不对，不应该，因为后面还有3，2，1 所以应该把4跳过去，待会从小的数开始数。再后面是200，因为没有199，所以应该从200开始。
或者这样看，每一个连续序列都可以被这个序列的最小值代表，要找到最小值才开始数，这样无重复，才能做到o(N)
具体来看，这个代码做了三个o(N)的操作： 1. 建dict 2. for循环里，看每一个数字n是否有n-1存在 3. while循环，从小到大的数连续序列
class Solution:
def longestConsecutive(self, nums) -> int:
max_len, table = 0, {num:True for num in nums}
for lo in nums:
if lo - 1 not in table:
hi = lo + 1
while hi in table:
hi += 1
max_len = max(max_len, hi - lo)
return max_len
暴力
public class Solution {
/**
* @param nums: A list of integers
* @return an integer
*/
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
int longest = 0;
for (int i = 0; i < nums.length; i++) {
int down = nums[i] - 1;
while (set.contains(down)) {
set.remove(down);
down--;
}
int up = nums[i] + 1;
while (set.contains(up)) {
set.remove(up);
up++;
}
longest = Math.max(longest, up - down - 1);
}
return longest;
}
}